Benchmark of popular graph/network packages v2

Main Updates

Here is a list of major developments since my previous post in April 2019:

• Python packages are now benchmark using timeit instead of cprofile for more accurate run time and to allow for better comparison across packages¹

• Results are compared using the median run time instead of the mean.²

• For all packages, the dataset is read as a directed graph and the benchmark time covers both the analytical run time as well as memory allocation.³

• Lightgraphs v2.0-dev is included in the benchmark exercise.⁴ It is the first Julia library to be added to the study – read on to find out how it fares with the rest.

• igraph, the incumbent in the space with popular R, Mathematica and Python bindings has been updated to v0.8. The last major release was way back in 2014! For a full list of new features and improvements, check out igraph’s github release page

• SNAP, another stalwart in the space releases v5.0, which finally supports Python 3 and pip install.

• Networkit releases v6.0.

• Streamline installation procedures for SNAP, graph-tool and networkit as they now support conda or pip. Check out my setup instructions to see how simple it is to install one of these packages now!

The changes to the benchmark methodology as well as standardisation of how the data is read and results are displayed allows for better comparisons to be drawn between packages.

At the same time the new features and improvements across the packages have made high-performance network analytics extremely accessible to any analyst out there – kudos to all the developers who have made this possible.

Methodology

The benchmark was carried out using a Google Compute n1-standard-16 instance (16vCPU Haswell 2.3GHz, 60 GB memory). Please refer to the setup folder for more detailed installation instructions.

Where applicable, all algorithms were tested using all 16 cores. I compared 6 different packages:

• graph-tool, v2.31 (Peixoto 2014)
• igraph, v0.8.2 (Csardi and Nepusz 2006)
• networkit, v6.1.0 (Staudt, Sazonovs, and Meyerhenke 2016)
• networkx, v2.4 (Hagberg, Swart, and S Chult 2008)
• SNAP, v5.0.0 (Leskovec and Sosič 2016)
• lightgraphs, v2.0-dev (Seth Bromberger and contributors 2017)

Networkx is written in Python while the other four packages, with the exception of lightgraphs, are based on C / C++ but have Python APIs. Igraph has an R and Mathematica binding as well though the benchmark was carried out on the Python one. Lightgraphs offers a performant platform for network and graph analysis in Julia.

Selecting what tasks to compare on is not really a trivial decision with each package offering various tools and capabilities. In the end, I decided to focus on 5 specific problems:

• loading the data
• single source shortest path
• page rank
• k-core decomposition
• strongly connected components

Loading is more of an I/O task while the other 4 are common graph algorithms.

Disclaimer:

• As far as possible, I try to specify the same parameters for each algorithm but differences in API across the packages could translate to actual differences in how the algorithm is run and the final output. For example, some of the observed differences in performance might be a result of different stopping criteria used or different algorithm implementations etc.

• For lightgraphs, the data is represented using the SimpleGraphs structure. Better performance could be achieved by using the StaticGraphs structure at the expense of mutability.

• The performance benchmark captures run time differences across packages on basic graph algorithms on directed graphs. Other important metrics such as memory consumption are out of scope of this study. Differences in implementation between directed and undirected graphs or weighted and non-weighted algorithms limit the generalisability across the other functions.

Dataset

3 datasets from the Stanford Large Network Dataset Collection (Leskovec and Krevl 2014) were used in the exercise:

• Amazon product co-purchasing network from March 2 2003, 262k nodes, 1.2m edges
• Web graph from Google, 875k nodes, 5.1m edges
• Pokec online social network, 1.6m nodes, 30.6m edges

While it is the easiest to rank the packages based on the run-time of the algorithms, it is only one of the many considerations of what makes a good package. I try to offer a more subjective view based on my experience with these packages.

Related Benchmarks

Here’s a list of other comparative benchmarks for the interested viewer to check out:

• Graph-tool performance comparison (Peixoto 2015), compares graph-tool with igraph and networkx on the single-source shortest path, page rank, k-core, minimum spanning tree and betweeness algorithms.

• Leskovec and Sosic (2016), compares snap with igraph and networkx on Erdos-Renyi graph generation and loading, page rank, clustering coefficient, weakly connected components, extracting 3-core of a network, and testing edge existence.

• Staudt, Sazonovs, and Meyerhenke (2016), compares networkit with igraph and graph-tool on the breadth-first search, connected components, core-decomposition, calculating the diameter of a graph, community detection, cluster coefficient, page rank, betweeness algorithms.

• Graph500 (Murphy et al. 2010), a notable graph based benchmark based on breadth-first search mostly to benchmark supercomputers rather than packages.

Most of the package comparison studies were written in 2015/2016. Since then, there have been substantial improvements in the field and it will be interesting to see the changes over time.

Results

All reported times are the median of that captured for a particular task. For the Amazon and Google dataset, all algorithms were run 100 times, while for the Pokec dataset 10 runs were carried out for each package. Networkx is the exception. Since it is slower by a significant magnitude (~approx 10 times than the slowest library), only 10 runs were carried out on the Amazon and Google dataset and 1 run on the Pokec dataset. For example, it took 68s to run the single source shortest path problem on the Pokec dataset on networkx compared to 0.62s for networkit (the next slowest). Hence, I left it out of the comparison plots.

Here are the run times of the other packages across the 3 benchmark datasets:

Full results can be seen from the table below:

Another way of looking at the results is by calculating the number of times one could run a particular algorithm given the time taken by networkx. This metric gives an indication of how many times more performant is a particular algorithm compared to networkx. The score calculated using the Google dataset is displayed below:

nx.shortest_path_length(g, nodeid)

g.shortest_paths([g.vs[node_index]])[0]

shortest_distance(g, g.vertex(node_index)).a

distance.BFS(g, node_index, storePaths=False).run().getDistances(False)

NIdToDistH = snap.TIntH()
snap.GetShortPath(g, node_index, NIdToDistH, True)
[(item, NIdToDistH[item]) for item in NIdToDistH]

distances(g, node_index, BreadthFirst(sort_alg=RadixSort)) # Non-threaded
distances(g, node_index, ThreadedBreadthFirst()) # Threaded

Conclusion

Here are my three main takeaways from this study. First, it is much easier to install any of these packages. One no longer needs to dig through all the documentation and fiddle around with installation. Most packages can now be installed from popular package managers with a single line. Some even offer docker builds.

Second, there has been a significant improvement across all packages. I am not sure whether this is because network analysis has become more popular or it is just a nice coincidence that most of the package maintainers decided to release major updates in 2019. Either way, it’s good news to end-users who can enjoy 2-10x speedup on popular algorithms.

Third, for most of these packages, the run time of an algorithm is relatively comparable especially if it is based on a compiled language (C, C++, Julia). See the connected component results for an example. If speed is of utmost importance than finding the right package that implements a threaded version of the algorithm is probably the next consideration.

If you are looking for recommendations on packages coming from a R / Python background (like myself), I would recommend networkx to pick up the basics of graph algorithms. If you are looking for a next step up and a more performant solution, igraph and graph-tool and networkit seem like good choices, provided the out of the box algorithms offer all that you need. If you are willing to consider a new language, lightgraphs is very promising and seem to have a lower learning curve than other C / C++ alternatives. Of course, if you have a specific problem to solve – it is certainly worth to benchmark it, given that no package is broadly superior to all others. In that case, feel free to extend on my code and modify it to suit your needs.

References

1. There is additional overhead from profiling code compared to just timing it.↩

2. Median is more robust to outliers. Full results – min, median, mean, max are all available in the respective output files for each profiling run for a dataset.↩

3. This makes comparisons between packages more comparable compared to the previous run.↩

4. Initial results based on v1.3 were committed to the repository in the beginning of the year. This revised benchmark uses v2.0-dev which can be pulled from the master branch.↩

5. A pure construction based benchmark exercise is probably required to separate the two factors.↩

6. Graph-tool should read from other file types such as graphml or dot much faster though I did not actually try it out.↩

7. Note: this might be due to differences in stopping criteria. Matthew Galati from SAS pointed out that for the page rank algorithm, networkit (as of version 6.0) uses L2 norm as a stopping criteria while other packages use the L1 norm. This means that it is doing fewer iterations and the speed is somewhat artificial↩

8. This paragraph is based on my experience re-running the previous benchmark before making changes to the codes. Due to differences in methodology, i.e. timeit vs cprofile as well as median vs mean, one should expect all the results to be lower than the previous runs – which they are. I highlight results which differ significantly from the previous run.↩

9. Graph-tool and networkit rely on openmp and one can set the number of threads using the openmp_set_num_threads function or setNumberOfThreads functions repectively. For lightgraphs, JULIA_NUM_THREADS environment variable has to be configured before running the multi-threaded functions.↩

10. lightgraphs offer an explicit threaded or non-threaded version of the algorithm. Single thread results for lightgraphs are reported using the non-threaded algorithm run on a single core.↩

11. The ‘non-threaded’ version is using BLAS which is inherently multi-threaded.↩

12. This is based on the development version of Lightgraphs v2.0-dev. Users of existing 1.x versions might find it slightly different.↩