This is interesting for Julia, because the library formerly known as LightGraphs usually compares quite favorably in performance to other libraries; in particular those with a Python interface. Based on the benchmarks linked above, it seems retworkx is faster. Another piece of data: I wrote the betweeness centrality function for retworkx (in the Rust layer). It was the first thing I ever wrote in Rust. But, at the Python level, it outperformed LightGraphs by 50% or so in tests I made while developing. I would like to better understand the data structures used by petgraph to see what their role is; I suspect itâs large.
The comparisons above implement solutions to the DIMACS 9 challenge. I started to implement this in Julia. But, I stalled a bit because despite some effort, I was unable to get a Julia implementation that is competitive with any of the entrants in that repo on the first step, which is graph construction. Of course, this is known to be Graphs.jl (former LG) 's weakest point. Also I did some yak shaving regarding the DIMACS file format; i.e. I might as well make a PR to GraphsIO.jl. But, 1) GraphsIO does not currently support reading attributes, so I would have to introduce a new dependency and extend the interface of loadgraph. 2) which attribute-bearing Julia structure is best for this is not clear, probably MetaGraphs. 3) DIMACS graph file format is apparently widely used in academic research, but it is unfortunately ill-specified and not versioned.
Seth gave an explanation in a Discourse post for why Graphs.jl is slow in reading graphs from files. But, in contrast, I found that, if I built only a SimpleGraph and did not use the weights from the DIMACS file, I could outperform all Python libraries except retworkx, and the latter was only 50% faster or so. I could even parse the weights and put them in an Array and be fast. I just could not put them in a graph structure without taking five times longer than (pure-Python) networkx. It seemed that the problem was the very large memory usage due to nested Dicts.
At any rate, I want to give this a bit of visibility because, aside from being an impressive library, retworkx represents a challenge to the Julia community.
Hi! Thank you for the post, I didnât know about retworkx and it looks pretty exciting!
Which structure / package did you use to create the graph? If it is MetaGraphs.jl, then Iâm not surprised it was slow, and alternative packages are (more or less) in the works
I tried both SimpleWeightedGraphs and MetaGraphs. The former was very slow. Contstructing the latter began rather quickly, but slowed down as edges were added. The challenge graph has about 6 x 10^7 edges. I saw there is an âexperimentalâ replacement for MetaGraphs, but did not try that.
SimpleWeightedGraphs use a CSC matrix for storage so mutating them is really slow. Constructing it should be as fast as suitsparseâs routine to go from [(rowind, colind,value)] format to CSC.
In a hypothetical version 2.0 of Graphs.jl, it would be nice to make the AbstractGraph interface more generic so that it is easier to use graph metadata. Right now there are various issues with attempting to use metadata or attempting to use labels for vertices that are not integers. There are some old issues in the LightGraphs.jl repo that I opened a while ago:
In my opinion, add_vertex!, rem_vertex!, add_edge!, and rem_edge! all need to be added as optional parts of the AbstractGraph interface. There needs to be a generic API for those functions that can apply to any mutable graph.
Well, theyâre optional in the sense that theyâre not mentioned at all in the API. What I mean is that they should be mandatory for mutable graphs (which is most graphs), and a generic API for those functions should be defined for all AbstractGraphs.
I would like to better understand the data structures used by petgraph to see what their role is; I suspect itâs large.
For petgraph the data structure retworkx is using (because petgraph actually offers several different types) is the StableGraph struct which is basically an adjacency list. The core of the data structure is 2 Rust Vecs containing nodes and edges. The edges for a node are stored kind of like a linked list of edge indices with the first edge index being stored in the Node struct and then each edge struct stores the index of the next edge. The stable graph part is just built on the Graph struct (which I used for the links above) and basically maintains a removed node and edge list to invalidate and preserve indices on removal while a normal Graph struct will swap_remove (to avoid the left shift overhead) which changes all the indices on removal. This ends up being quite performant because at the end of the day most of the graph operations are just operating on a Vec which is very quick (and works nicely with CPU caching).
I wrote the betweeness centrality function for retworkx (in the Rust layer). It was the first thing I ever wrote in Rust. But, at the Python level, it outperformed LightGraphs by 50% or so in tests I made while developing.
retworkx will be be a bit faster now that we introduced the multithreaded implementation of betweenness centrality.
For retworkx if youâre not interacting with node weights there is almost no overhead from python aside from the python function call overhead and any argument copy and type conversion from python ->rust (which except for complicated or large data inputs that need to be copied and/or converted is on the order of 100s of ns) and potentially the same copy/convert for the return to python (but in this case itâs ameliorated by using a custom rust pyclass return that avoids the copy/convert until individual elements are accessed). This is because retworkx stores the node and edge weights as basically pointers to the Python heap, so we only interact with Python when we need to inspect a weight object. So for betweenness centrality where itâs all isolated to the structure of the graph itâs basically all native rust performance since youâre working solely in rust without needing to check node or edge weights.
For other algorithms that need to interact with weights (like edge weights in a shortest path) we have more overhead because we have to use a callback to python to get a statically typed weight from a given python object. You can see this in the benchmarks, retworkx is a bit slower for the single source shortest path and Iâm like 90% sure thatâs the python callback overhead.
But, I stalled a bit because despite some effort, I was unable to get a Julia implementation that is competitive with any of the entrants in that repo on the first step, which is graph construction.
For those benchmarks I wanted to be as fair as I could for all the python libs so I didnât use a reader written in rust (which would be significantly faster) and just opened the file in Python and manually called graph.add_node() and graph.add_edge() (or the equivalents) in each python library while iterating over each line (with the exception of python-igraph which creates a networkx graph first and converts it, for whatever reason this was significantly faster than creating it directly). This way each lib had a baseline of pythonâs file reader performance and iterating over the file. Iâve not really worked in Julia much, but is doing normal text file io and calling the individual graph library calls not an option, I would assume Juliaâs file I/O is faster than Pythonâs. Or is that what you were trying?
I guessed you did it this way because it was simple and perhaps a native reader would be overoptimizing compared to constructing the graph. I think writing the reader in rust (with a Python interface) is perhaps fair. It certainly would be if the graph format were a solid standard (it is not). I was spending some time getting the parsing as fast as I could in Julia (I posted here ) But, constructing a graph with weights swamped this time. It would be easy to test your python reader at just parsing (has the advantage of being very readable code) vs. Julia at just parsing.
Julia can call into Rust just fine (e.g. via RustCall.jl or provided the rust library gives us C bindings to call), so that should definitely work. The trouble is of course that we often want our cake and eat it too - in this case, that means having multithreading compose. While julia composes multithreading internally just fine, it doesnât across a ccall boundary (or any FFI boundary, really). Iâm guessing thatâs where a lot of the desire for having a julia-native version comes from.
Other than that, we love us some speed in julia as well, so sometimes itâs just for the challenge of it
I was actually asking about this more as an approach for using the Julia graph library, but thatâs because I misread the OP and didnât see most of the time was spent in the actual graph object construction.
That being said, I hadnât actually thought about calling to into petgraph/retworkx from Julia to reuse the implementations there. Itâs an interesting idea, and adding a native C FFI to retworkx is something Iâve had as a long term TODO see: https://github.com/Qiskit/retworkx/issues/33 Although when I opened that issue it was primarily to expose a C api to other compiled Python extensions (like numpyâs C api that cython and other extensions can use). But, now that we have a native rust library maybe just putting a more generic C api in front of that would be useful too.
