基准测试#
本页介绍 `nx-cugraph` 当前支持的算法在四种不同大小图上的性能表现。
目的是清晰比较将任务调度到 GPU 加速后端与默认的基于 CPU 的 NetworkX 实现之间的性能差异。这让用户了解通过使用 `nx-cugraph` 将任务调度到 GPU 可能获得的潜在加速。
随着数据集变大，GPU 加速后端通常会开始显示出比 CPU 更快的加速。这一趋势表明了 GPU 的并行处理能力如何使其比 CPU 更有效地处理大规模图分析。
数据集#
基准测试中使用的数据集是
| 数据集 | 节点数 | 边数 | 描述 |
|---|---|---|---|
| netscience | 1,461 | 5,484 | 一个小型有向图，代表一个科学合作网络。 |
| amazon0302 | 262,111 | 1,234,877 | 一个中型无向图，模拟产品共同购买数据。 |
| cit-Patents | 3,774,768 | 16,518,948 | 一个大型有向图，代表美国专利引用关系。 |
| soc-LiveJournal1 | 4,847,571 | 68,993,773 | 一个基于 LiveJournal 社交网络的超大型有向图。 |
算法表#
下表展示了在四种数据集之一上运行特定算法时 CPU 和 GPU 之间的性能差异。
每个单元格显示在 `nx-cugraph` 上运行算法相对于默认 NetworkX 实现所达到的加速因子。值越高表示性能越好。为了提高可读性，单元格根据以下加速标准进行颜色编码
绿色表示优秀 (>5.0)
黄色表示中等 (1.1 - 5.0)
红色表示不理想 (0 - 1.0)
此外，将鼠标悬停在表格上，用户可以看到 NetworkX 和 nx-cugraph 分别花费的时间，以及两次运行之间的差值。我们鼓励用户参考此表，以了解他们的工作流程可能获得的近似性能提升。
| 算法 | 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 |
* 表示 CPU 和 GPU 之间的时间差异不显著 (<1s)