Benchmarks#

This page presents the performance of algorithms currently supported by nx-cugraph across four graphs of varying sizes.

The goal is to provide a clear comparison of how dispatching to a GPU-accelerated backend compares against the default, CPU-based implementation of NetworkX. This allows users to get an idea of potential speedups that they might see by leveraging dispatching to a GPU with nx-cugraph.

As datasets grow larger, the GPU-accelerated backend typically begins to show increasingly faster speedups over the CPU. This trend demonstrates how the GPU’s parallel processing capabilities allow it to handle large-scale graph analytics much more efficiently than the CPU.

Datasets#

The datasets used in the benchmarks are:

Dataset Number of Nodes Number of Edges Description
netscience 1,461 5,484 A small, directed graph representing a scientific collaboration network.
amazon0302 262,111 1,234,877 A medium, undirected graph modeling product co-purchasing data.
cit-Patents 3,774,768 16,518,948 A large, directed graph representing U.S. patent citation relationships.
soc-LiveJournal1 4,847,571 68,993,773 A very large, directed graph based on the LiveJournal social network.


Algorithm Table#

The table below showcases the performance difference between CPU and GPU when running a particular algorithm on one of the four datasets.

Each cell displays the speedup factor achieved when running the algorithm on a nx-cugraph compared to default NetworkX. A higher value indicates better performance. To enhance readability, the cells are color-coded based on the following speedup criteria:

  • Green for excellent (>5.0)

  • Yellow for moderate (1.1 - 5.0)

  • Red for suboptimal (0 - 1.0)

Also, by hovering over the table, users can see the time it took for NetworkX and nx-cugraph respectively, as well as the delta between both runs. We encourage users to refer to this table to see an approximation of the performance increase they can expect from their workflows.

Algorithm netscience amazon0302 citpatents livejournal
ancestors 0.089*nx: 491.479us
nxcg: 5.497ms
delta: -5.005ms
60.463nx: 1.712s
nxcg: 28.310ms
delta: 1.683s
0.134*nx: 4.359ms
nxcg: 32.491ms
delta: -28.132ms
78.609nx: 56.688s
nxcg: 721.145ms
delta: 55.967s
average_clustering 1.619*nx: 14.918ms
nxcg: 9.213ms
delta: 5.706ms
293.432nx: 6.745s
nxcg: 22.988ms
delta: 6.722s
868.635nx: 181.956s
nxcg: 209.474ms
delta: 181.747s
2828.128nx: 2151.410s
nxcg: 760.719ms
delta: 2150.649s
betweenness_centrality, k=10 0.274*nx: 5.449ms
nxcg: 19.923ms
delta: -14.474ms
56.98nx: 14.256s
nxcg: 250.186ms
delta: 14.005s
99.364nx: 95.752s
nxcg: 963.653ms
delta: 94.789s
264.882nx: 610.395s
nxcg: 2.304s
delta: 608.091s
betweenness_centrality, k=100 0.239*nx: 42.450ms
nxcg: 177.676ms
delta: -135.225ms
50.352nx: 110.614s
nxcg: 2.197s
delta: 108.417s
520.555nx: 966.550s
nxcg: 1.857s
delta: 964.694s
487.469nx: 6688.933s
nxcg: 13.722s
delta: 6675.211s
bfs_edges 0.035*nx: 295.556us
nxcg: 8.488ms
delta: -8.192ms
0.383nx: 1.260s
nxcg: 3.292s
delta: -2.032s
0.003*nx: 115.556us
nxcg: 35.910ms
delta: -35.794ms
2.141nx: 75.646s
nxcg: 35.329s
delta: 40.318s
bfs_layers 0.046*nx: 307.147us
nxcg: 6.690ms
delta: -6.383ms
9.489*nx: 327.838ms
nxcg: 34.548ms
delta: 293.290ms
0.004*nx: 122.647us
nxcg: 32.934ms
delta: -32.811ms
33.468nx: 16.313s
nxcg: 487.419ms
delta: 15.825s
bfs_predecessors 0.04*nx: 336.403us
nxcg: 8.442ms
delta: -8.106ms
0.389nx: 1.282s
nxcg: 3.293s
delta: -2.011s
0.004*nx: 139.603us
nxcg: 35.985ms
delta: -35.845ms
1.728nx: 61.628s
nxcg: 35.664s
delta: 25.964s
bfs_successors 0.039*nx: 329.301us
nxcg: 8.441ms
delta: -8.112ms
0.491nx: 1.802s
nxcg: 3.669s
delta: -1.866s
0.004*nx: 130.468us
nxcg: 35.864ms
delta: -35.733ms
1.822nx: 62.495s
nxcg: 34.297s
delta: 28.198s
bfs_tree 0.121*nx: 855.597us
nxcg: 7.060ms
delta: -6.204ms
58.569nx: 2.929s
nxcg: 50.011ms
delta: 2.879s
0.011*nx: 403.871us
nxcg: 35.151ms
delta: -34.748ms
55.688nx: 74.665s
nxcg: 1.341s
delta: 73.324s
clustering 1.596*nx: 14.618ms
nxcg: 9.162ms
delta: 5.456ms
136.185nx: 6.775s
nxcg: 49.747ms
delta: 6.725s
168.938nx: 181.769s
nxcg: 1.076s
delta: 180.693s
1132.732nx: 2149.226s
nxcg: 1.897s
delta: 2147.328s
core_number 0.223*nx: 2.372ms
nxcg: 10.652ms
delta: -8.280ms
22.456nx: 1.520s
nxcg: 67.706ms
delta: 1.453s
-- --
degree_centrality 0.331nx: 361.917us
nxcg: 1.092ms
delta: -730.266us
2.834*nx: 75.040ms
nxcg: 26.474ms
delta: 48.566ms
2.037*nx: 1.565s
nxcg: 768.326ms
delta: 796.394ms
2.045nx: 2.048s
nxcg: 1.002s
delta: 1.047s
descendants 0.059*nx: 325.657us
nxcg: 5.552ms
delta: -5.226ms
38.477nx: 1.259s
nxcg: 32.708ms
delta: 1.226s
0.004*nx: 127.983us
nxcg: 31.525ms
delta: -31.397ms
82.354nx: 61.836s
nxcg: 750.849ms
delta: 61.085s
descendants_at_distance 0.007*nx: 26.257us
nxcg: 3.593ms
delta: -3.567ms
0.003*nx: 20.914us
nxcg: 6.145ms
delta: -6.124ms
0.001*nx: 32.306us
nxcg: 30.265ms
delta: -30.233ms
0.065*nx: 5.894ms
nxcg: 90.867ms
delta: -84.973ms
edge_betweenness_centrality, k=10 0.167*nx: 7.114ms
nxcg: 42.690ms
delta: -35.576ms
14.605nx: 18.773s
nxcg: 1.285s
delta: 17.488s
10.153nx: 121.627s
nxcg: 11.979s
delta: 109.647s
16.778nx: 909.093s
nxcg: 54.182s
delta: 854.911s
edge_betweenness_centrality, k=100 0.15*nx: 43.901ms
nxcg: 292.226ms
delta: -248.325ms
24.172nx: 172.498s
nxcg: 7.136s
delta: 165.361s
68.332nx: 972.557s
nxcg: 14.233s
delta: 958.325s
112.81nx: 8546.360s
nxcg: 75.759s
delta: 8470.601s
ego_graph 0.726*nx: 5.584ms
nxcg: 7.693ms
delta: -2.109ms
104.093nx: 5.857s
nxcg: 56.265ms
delta: 5.801s
0.008*nx: 1.431ms
nxcg: 187.666ms
delta: -186.235ms
150.036nx: 302.519s
nxcg: 2.016s
delta: 300.503s
eigenvector_centrality 7.409*nx: 28.642ms
nxcg: 3.866ms
delta: 24.776ms
-- 263.997nx: 242.879s
nxcg: 920.007ms
delta: 241.959s
376.161nx: 458.153s
nxcg: 1.218s
delta: 456.935s
generic_bfs_edges 0.032*nx: 276.460us
nxcg: 8.570ms
delta: -8.294ms
0.38nx: 1.238s
nxcg: 3.256s
delta: -2.018s
0.003*nx: 109.543us
nxcg: 35.921ms
delta: -35.811ms
2.129nx: 75.324s
nxcg: 35.374s
delta: 39.949s
hits 1.703*nx: 7.290ms
nxcg: 4.280ms
delta: 3.010ms
-- 33.932nx: 64.038s
nxcg: 1.887s
delta: 62.150s
87.124nx: 233.893s
nxcg: 2.685s
delta: 231.209s
in_degree_centrality 0.459nx: 293.520us
nxcg: 639.090us
delta: -345.570us
2.095*nx: 57.231ms
nxcg: 27.314ms
delta: 29.917ms
1.645*nx: 1.275s
nxcg: 775.082ms
delta: 499.672ms
1.808*nx: 1.798s
nxcg: 994.536ms
delta: 803.470ms
is_weakly_connected 0.001*nx: 28.767us
nxcg: 31.511ms
delta: -31.482ms
9.442*nx: 469.725ms
nxcg: 49.747ms
delta: 419.978ms
52.655nx: 10.313s
nxcg: 195.850ms
delta: 10.117s
64.03nx: 22.803s
nxcg: 356.123ms
delta: 22.446s
k_truss 8.31*nx: 12.342ms
nxcg: 1.485ms
delta: 10.857ms
539.652nx: 6.103s
nxcg: 11.309ms
delta: 6.092s
-- --
katz_centrality 122.153nx: 4.219s
nxcg: 34.535ms
delta: 4.184s
648.055nx: 24.870s
nxcg: 38.376ms
delta: 24.831s
300.147nx: 274.585s
nxcg: 914.835ms
delta: 273.670s
24767.824nx: 76304.239s
nxcg: 3.081s
delta: 76301.159s
louvain_communities 2.479*nx: 72.361ms
nxcg: 29.185ms
delta: 43.176ms
103.205nx: 43.659s
nxcg: 423.034ms
delta: 43.236s
272.652nx: 2409.300s
nxcg: 8.837s
delta: 2400.464s
208.843nx: 4291.899s
nxcg: 20.551s
delta: 4271.348s
number_weakly_connected_components 0.041*nx: 1.296ms
nxcg: 31.745ms
delta: -30.449ms
9.956*nx: 493.798ms
nxcg: 49.599ms
delta: 444.199ms
54.189nx: 10.795s
nxcg: 199.216ms
delta: 10.596s
64.136nx: 23.510s
nxcg: 366.558ms
delta: 23.143s
out_degree_centrality 0.453nx: 287.390us
nxcg: 634.436us
delta: -347.046us
2.156*nx: 58.691ms
nxcg: 27.227ms
delta: 31.464ms
1.549*nx: 1.202s
nxcg: 775.760ms
delta: 426.122ms
1.727*nx: 1.714s
nxcg: 992.363ms
delta: 721.574ms
overall_reciprocity 7.901*nx: 15.359ms
nxcg: 1.944ms
delta: 13.415ms
563.312nx: 4.525s
nxcg: 8.032ms
delta: 4.517s
1524.889nx: 78.576s
nxcg: 51.529ms
delta: 78.524s
2257.021nx: 239.907s
nxcg: 106.294ms
delta: 239.801s
pagerank 1.696*nx: 6.589ms
nxcg: 3.885ms
delta: 2.704ms
76.288nx: 2.828s
nxcg: 37.065ms
delta: 2.791s
82.128nx: 72.134s
nxcg: 878.314ms
delta: 71.256s
188.302nx: 223.766s
nxcg: 1.188s
delta: 222.578s
pagerank_personalized 1.406*nx: 6.942ms
nxcg: 4.939ms
delta: 2.003ms
55.666nx: 3.265s
nxcg: 58.648ms
delta: 3.206s
46.6nx: 65.932s
nxcg: 1.415s
delta: 64.517s
120.002nx: 237.002s
nxcg: 1.975s
delta: 235.027s
reciprocity 0.01*nx: 22.615us
nxcg: 2.313ms
delta: -2.291ms
0.013*nx: 43.303us
nxcg: 3.431ms
delta: -3.388ms
0.009*nx: 54.886us
nxcg: 5.864ms
delta: -5.809ms
0.172*nx: 2.705ms
nxcg: 15.737ms
delta: -13.032ms
shortest_path 0.064*nx: 393.284us
nxcg: 6.105ms
delta: -5.711ms
1.1*nx: 960.214ms
nxcg: 872.857ms
delta: 87.358ms
0.005*nx: 168.884us
nxcg: 33.088ms
delta: -32.919ms
1.344nx: 49.690s
nxcg: 36.964s
delta: 12.726s
single_source_shortest_path_length 0.042*nx: 235.942us
nxcg: 5.613ms
delta: -5.377ms
6.285*nx: 280.148ms
nxcg: 44.572ms
delta: 235.576ms
0.003*nx: 89.561us
nxcg: 31.926ms
delta: -31.836ms
14.241nx: 15.347s
nxcg: 1.078s
delta: 14.269s
single_target_shortest_path_length 0.042*nx: 240.253us
nxcg: 5.682ms
delta: -5.442ms
5.482*nx: 290.073ms
nxcg: 52.910ms
delta: 237.162ms
0.098*nx: 3.321ms
nxcg: 33.767ms
delta: -30.446ms
7.672nx: 11.358s
nxcg: 1.480s
delta: 9.878s
transitivity 1.682*nx: 15.338ms
nxcg: 9.116ms
delta: 6.222ms
331.111nx: 7.525s
nxcg: 22.726ms
delta: 7.502s
937.121nx: 196.579s
nxcg: 209.769ms
delta: 196.369s
2831.727nx: 2157.310s
nxcg: 761.836ms
delta: 2156.548s
triangles 0.625*nx: 5.069ms
nxcg: 8.105ms
delta: -3.036ms
56.354nx: 2.591s
nxcg: 45.977ms
delta: 2.545s
55.831nx: 55.304s
nxcg: 990.560ms
delta: 54.313s
124.634nx: 220.697s
nxcg: 1.771s
delta: 218.926s
weakly_connected_components 0.035*nx: 1.275ms
nxcg: 36.601ms
delta: -35.326ms
7.677*nx: 493.186ms
nxcg: 64.240ms
delta: 428.946ms
11.559nx: 10.928s
nxcg: 945.427ms
delta: 9.983s
20.597nx: 24.027s
nxcg: 1.167s
delta: 22.861s

* indicates that the time difference between CPU and GPU was insignificant (<1s)