The LightGraphs team has new independent benchmarks to report. Tim Lin published a blog post last year comparing five popular graph packages. All were Python-based; all but one was a two-language (C/C++) package. The results were predictable: the Python-only package (NetworkX) got trounced.
I reached out to Tim in January to see whether he’d be interested in doing an update including LightGraphs as another single-language package. He agreed, and updated the results two weeks ago.
The takeaways:
LG performed admirably on all tests except for k-core / decomposition and graph loading. The k-core results can be explained by two things: first, the fastest implementation (NetworKit) appears to be parallelized; LG’s decomposition is (currently) serial. Second, the benchmark did not use our latest code, which provides roughly a 4x speedup (note: this is on different hardware so the relative timings are the important data.) Tim will be re-running his benchmarks in April and the new code will be used then. We expect to be very competitive with the single-core implementations out there.
The time it takes to load a graph from an edge list is, frankly, not a performance objective for LG at this time since there are a whole slew of interrelated dependencies and variables that will be hard to optimize, and graph loading is generally a one-shot operation anyway.
For pagerank, the results are solid. We do very well in small and medium graphs, essentially tying/beating the other fastest tool (NetworKit), but they’re using different termination criteria than anyone else, and their choice confers a performance advantage at the possible expense of accuracy. On the largest graph, we are ~2.5x slower than NetworKit but still in second place, beating the third-place finisher by ~3x.
For connected components, we come in slightly (between 10% and 18%) behind the first place (graph-tool), but well ahead of the third place finisher (between 1.7 and 4x faster).
Where we really shine is in shortest path calculations. We consistently beat the second-place performer (graph-tool) by as much as 3x.
Here are our place rankings for each graph size:
| Test | Small | Medium | Large | Notes |
|–|–|–|–|–|–|
| Connected components | 2 | 2 | 2 | Graph-tool between 0 and 18% faster |
| K-core | 5 | 5 | 5 | Old LG code used; new code gives 4x speedup which would put us in 2nd place behind NetworKit |
| Loading | 5 | 4 | 5 | Not a performance objective for us |
| Pagerank | 2 | 1 | 2 | NetworKit uses a different termination and is up to 2x faster as a result |
| Shortest paths | 1 | 1 | 1 | LG consistently wins here by 2-3x |
The bottom line…
…is that LG is competitive across the board against all of the packages tested, and is probably a better general choice when compared head-to-head with any individual package. We’re also the only performant single-language library tested.
We’ll report out on the April benchmarks as soon as we get them.
Thanks to everyone who made these results possible, and to our users who continue to challenge us to do better.