Graph-tool performance comparison
This page shows a succinct performance comparison between graph-tool and two other popular graph libraries with Python bindings, igraph and NetworkX. NetworkX is a pure-python implementation, whereas igraph is implemented in C. Here we select a few representative algorithms which are implemented in all three libraries, and test them on the same graph.
The graph used here is the strongly connected component of the PGP web of trust network circa November 2009. It is a directed graph, with N=39,796 vertices and E=301,498 edges. The network and test scripts can be downloaded at the bottom of the page.
For this test we used graph-tool 2.33, igraph 0.8.2 and NetworkX 2.4.
The functions were called several times, and the average time taken per function call was computed and shown below. All results are for the same Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz with 8 cores and 16 threads. In the second column are shown the results for graph-tool with OpenMP enabled using 16 threads, and the third column shows the results using only one thread.
| Algorithm | graph-tool (16 threads) | graph-tool (1 thread) | igraph | NetworkX |
|---|---|---|---|---|
| Single-source shortest path | 0.0023 s | 0.0022 s | 0.0092 s | 0.25 s |
| Global clustering | 0.011 s | 0.025 s | 0.027 s | 7.94 s |
| PageRank | 0.0052 s | 0.022 s | 0.072 s | 1.54 s |
| K-core | 0.0033 s | 0.0036 s | 0.0098 s | 0.72 s |
| Minimum spanning tree | 0.0073 s | 0.0072 s | 0.026 s | 0.64 s |
| Betweenness | 102 s (~1.7 mins) | 331 s (~5.5 mins) | 198 s (vertex) + 439 s (edge) (~ 10.6 mins) | 10297 s (vertex) 13913 s (edge) (~6.7 hours) |
When OpenMP is disabled, both graph-tool and igraph seem to deliver an overall comparable performance. However, even in this case graph-tool seems to be faster systematically.
As expected, graph-tool becomes even faster when OpenMP is enabled on algorithms which run in parallel (PageRank, global clustering and betweenness), and thus beats igraph in these cases by a significant margin, which would increase even further for larger networks and machines with more cores.
NetworkX, on the other hand, comes at a distant third with running times in the order of 40 to 250 times slower than graph-tool. This is mostly due to its pure Python implementation, which is known to be in general substantially slower than C/C++ (see here and here for further comparisons).
One must remember that performance alone is not the only issue which should be considered. All these libraries have their own advantages and disadvantages, which need to be considered in detail when deciding what is the best library to use. Here are a couple of important facts:
- Graph-tool’s performance comes at the cost of increased time and memory required during compilation. This is mostly due to the in-place graph filtering functionality that the library provides, which none of the others do. Nevertheless, if one is using an operating system for which no pre-compiled binaries are available, this is an extra burden which the user should consider.
- The igraph library requires less resources for compilation, and comes with additional bindings for the R and C languages which the other two lack.
- NetworkX is comparatively very inefficient, but it is trivial to install — requiring no compilation at all, since it is pure python. Thus one can get started with very little to no effort. The speed may not be a problem if one is dealing with very small graphs, and does not care if an algorithm runs in, say, 1 or 30 seconds. However, if the graph size increases to hundreds of thousands, or millions of vertices/edges, this difference can scale up quickly.
Additionally, these libraries have different APIs and handle things slightly differently, and they may appeal to different user tastes. Furthermore the set of algorithms which is implemented is not identical. For instance, graph-tool has graph filtering, more extensive flow algorithms, stochastic block model inference, and interactive graph drawing, to name a few unique features. However, both NetworkX and igraph have their own unique features and algorithms which graph-tool currently lacks, and a detailed point-for-point comparison it is out of the scope of this brief analysis. In the end, it is up to the user to make a more detailed comparison and decide what is more appropriate.
Benchmark sources & outputs
Source Network: pgp.xml.gz, pgp_undirected.xml.gz
Graph-tool benchmark script: gt_bench.py
igraph benchmark script: igraph_bench.py
nx benchmark script: nx_bench.py
This page was last updated on 8 July 2020.
