TL;DR
- NetworkXはよく知られたPythonのネットワーク分析ライブラリだが、遅い
- 実験の結果、Rustで実装されたrustworkxが速く、さらにNetworkXからの置き換えやすさの観点で優れている
- NetworkXからrustworkxに置き換えたい人はここから読んでください
rustworkxの公式ドキュメントは以下です。
はじめに
こんにちは。ZENKIGENデータサイエンスチーム所属のredteaです。原籍はオムロンソーシアルソリューションズ株式会社 技術創造センタですが、社外出向でZENKIGENに所属しており、数理最適化や機械学習を用いたデータの分析業務、それらの結果に基づいた顧客への提案をしております[1]。
問題提起(NetworkXは遅い)
さて、Pythonをこよなく愛する皆様はグラフ/ネットワーク分析をするとき、どのライブラリを使っていますか？デファクトスタンダードとして有名なのはNetworkXですよね。NetworkXは非常に有名で、「Python ネットワーク分析」等でWEB検索すると解説記事がたくさん出てきます。さらに機能が充実しているため、やりたいことのほとんどはこのNetworkXで達成でき、Pythonユーザにとっては心強い存在です。
しかし、NetworkXは純粋なPythonで、しかも並列化せずに書かれているため[2]、動作が非常に遅いです。C言語などのコンパイル型言語で書かれ、並列処理に対応した、高速に動作するPythonのネットワーク分析ライブラリがあれば、それを使いたいはずです。
本記事でやること
本記事では、NetworkXに代わる、高速に動作するPythonのネットワーク分析ライブラリについて調査、共有します。具体的には以下の2つです。
- NetworkXを含むPythonのネットワーク分析ライブラリのパフォーマンス比較実験
- NetworkXから高速なrustworkxへの乗り換えのための使い方紹介
筆者が調べたところ、Pythonでネットワーク分析ができるライブラリはNetworkX以外にもrustworkxというRustで書かれたものや、NetworKitというC++の実装がありました[3]。
これらはコンパイル型言語で実装され[4]、さらに並列実行が可能なため、非常に高速に動作することが期待できます。また、筆者により実装したC言語版の実装(networkcと名付けました)を加えて、
- NetworkX
- networkc
- NetworKit
- rustworkx
の4つのライブラリ間でパフォーマンス比較します。
なお、networkcの実装は以下の通りです。
比較実験
実験設定
実験で使用したソースコードは以下に置いております。
タスク
dijkstra法による、各ノード間の最短経路の算出を実験タスクとします[5]。NetworkXでは、dijkstra法の実装に二分ヒープが用いられているため、計算量は、
エッジの密度
なお、実行時間を計測するのはあくまでもアルゴリズムの実行にかかる時間とし、グラフオブジェクトを作るなどの前処理にかかる時間は計測対象外とします。
対象ライブラリ
以下の4つのライブラリを比較対象とし、それぞれの条件は以下の表の通りです[7]。
| ライブラリ名 | dijkstra法の実装 | 言語 | 並列化 |
|---|---|---|---|
| NetworkX | 二分ヒープ | Python | なし |
| networkc | 二分ヒープ | C | なし |
| NetworKit | 二分ヒープ | C++ | あり[8] |
| rustworkx | 二分ヒープ | Rust | あり |
今回自作したnetworkcでは、dijkstra法を二分ヒープで実装し、並列化はしていません。すなわち、NetworkXと同じ条件で、単に言語が変わった条件(コンパイル型とインタプリタ型の差)と捉えることができます。また、networkcとrustworkxの比較により、並列化と非並列処理の差[9]を確認することができます。
実験環境
| 項目 | 値 |
|---|---|
| OS | Ventura 13.2.1 (macOS) |
| CPU | 3.49GHz 8cores (Apple M2) |
| RAM | 16GB |
結果
実験結果は以下の図の通り、NetworKitとrustworkxが頭ひとつ抜けている状態でした。横軸はdijkstra法を適用するグラフのノード数、縦軸が実行にかかった時間（秒）を表します。エッジ密度条件
NetworkXとnetworkcはノード数が多くなってくると計算時間が非常に長いため、ノード数3200以上の結果は割愛
次に
NetworkXとnetworkcはノード数が多くなってくると計算時間が非常に長いため、ノード数3200以上の結果は割愛
最後に、密な時(
NetworkXとnetworkcはノード数が多くなってくると計算時間が非常に長いため、ノード数3200以上の結果は割愛
以上、
NetworkXからrustworkxへの乗り換えについて
実験結果では、NetworKitもrustworkxに劣らない速さでしたが、rustworkxはNetworkXにインスパイアされて開発が進められており、NetworkXからの乗り換えやすさの観点から、本記事ではrustworkxへの乗り換え方法について紹介します。NetworKitも置き換えにくいわけではなく、是非NetworKitの公式ドキュメントを参照して使ってみてください。現状、私がNetworKitを詳しく知らないだけです。
前提
2024年2月現在の最新バージョンを想定しています。
| NetworkXのバージョン | rustworkxのバージョン |
|---|---|
| 3.2.1 | 0.13.2 |
rustworkxとは
rustworkx[11]はApache2.0ライセンスに基づいており、無料で商用利用可能なPythonのライブラリです。Rustの持つパフォーマンスを存分に発揮し、高速に動作します。
ただし、NetworkXのドロップイン置き換え[12]ではなくNetworkXからrustworkxに置き換えるには前処理や後処理が必要です。これはRustとPythonの制限の違いによって、やむなく若干の違いが生じています。
また、NetworkXの歴史は長く、かなり広範囲に機能が充実していますが、rustworkxは比較的新しく開発途上にあり、全てのNetworkXの機能を携えていません[13]。使いたい機能がrustworkxにあるかどうか確認する必要があります。
NetworkXからの乗り換え
本節は以下の記事を大いに参照しながら、NetworkXとrustworkxの違いを説明します。
主な違い
- rustworkxグラフのノードやエッジへのアクセスは整数インデックスによる[14]。
- rustworkxのアルゴリズム関数の多くは明確に型付けされているため、rustworkxグラフが
PyDiGraph(有向グラフ)かPyGraph(無向グラフ)かによって関数が分けられている[15]。
グラフコンストラクタ
| NetworkX | rustworkx |
|---|---|
Graph() |
PyGraph(multigraph=False) |
DiGraph() |
PyDiGraph(multigraph=False) |
MultiGraph |
PyGraph() |
MultiDiGraph() |
PyDiGraph() |
ノード、エッジの追加
| NetworkX | rustworkx | rustworkxに関する補足 |
|---|---|---|
add_node() |
add_node() |
rustworkxは戻り値としてノードのインデックスを返してくれる |
add_nodes_from() |
add_nodes_from() |
rustworkxではオブジェクトのリストを引数で渡して、戻り値はノードのインデックスのリストが返ってくる |
add_edge() |
add_edge() |
rustworkxは3つの引数(1つ目のノードインデックス、2つめのノードインデックス、 エッジに付与する情報[16]) |
add_edges_from() |
add_edges_from(), add_edges_from_no_data(), extend_from_edge_list(), extend_from_weighted_edge_list()
|
extend_from* ノードのインデックスが存在しない場合は、新しいノードを作る |
上記の表では、NetworkXはすべてGraph版を、
rustworkxは全てPyDiGraph版のリンクを貼っていますが、それぞれDiGraphやPyGraphでも利用できます。
rustworkxではコンストラクタ呼び出し時にグラフを初期化できない点は注意で、一度空っぽのグラフを作ってからノードやエッジを追加していく必要があります。
| NetworkX | rustworkx | rustworkxの補足 |
|---|---|---|
Graph([(0, 1), (1, 0)]) |
graph = PyGraph() graph.extend_from_edge_list([(0, 1), (1, 0)])
|
引数はlist[tuple[int, int]]
|
Graph(np.array([[0, 1, 1], [1, 0, 1], [1, 0, 1]])) |
PyGraph.from_adjacency_matrix(np.array([[0, 1, 1], [1, 0, 1], [1, 0, 1]], dtype=np.float64)) |
from_adjacency_matrix()はfloat型numpy配列のみ.astype(np.float64, copy=False)が便利 |
各リソースへのアクセス
| やりたいこと | NetworkX | rustworkx |
|---|---|---|
| ノードへのアクセス | ハッシュ可能なPythonオブジェクト graph.nodes["hashable obj"]
|
ノードの整数インデックス graph[0]
|
| エッジへのアクセス | 2つのノードIDを指定 graph.get_edge_data("node_a", "node_b")
|
エッジのインデックスを指定 graph.edges()[0]
|
ノード属性・エッジ属性
rustworkxのグラフには、任意のPythonオブジェクトをdictを用いることで付与することができます。
import rustworkx as rx
graph = rx.PyGraph()
node_a = graph.add_node({'time': '5pm'})
node_b = graph.add_nodes_from([{'time': '2pm'}])
graph[node_a]['room'] = 714
サンプルコード
前項までで表にまとめたことを、実際に動く[17]コードで確認します。
NetworkXは、ノードやエッジへのアクセスはノードID、エッジID[18]を指定することで実現できます。ノードID、エッジIDはhashableなpythonオブジェクトであればなんでも良いです。何でも良いので、以下の例のように、int型でもstr型でも、tuple[str, int]型、さらには自分で定義したクラスのインスタンスでも良いです。
import networkx as nx
graph = nx.DiGraph()
graph.add_node("node_a", value=1)
graph.add_node("node_b")
graph.add_node(2)
graph.add_node(("a", 2))
# ノードへのアクセスはノードオブジェクトで指定できる
print(graph.nodes["node_a"]) # {'value': 1}
# エッジの追加はノードオブジェクトで指定できる
graph.add_edge("node_a", "node_b", weight=1)
graph.add_edge(2, ("a", 2), weight=5)
# エッジへのアクセス
edge_data = graph.get_edge_data("node_a", "node_b")
print(edge_data["weight"]) # 1
一方、rustworkxでは、グラフ上に任意のPythonオブジェクトをアタッチできますが、各ノードとエッジには整数のインデックスが割り当てられます(ノードID、エッジIDに相当）。このインデックスは、グラフ上のノードとエッジにアクセスするときに使います。
import rustworkx as rx
graph = rx.PyDiGraph()
node_a = graph.add_node("my_node_a")
node_b = graph.add_node("my_node_b")
node_c = graph.add_node(2)
node_d = graph.add_node(("a", 2))
print(node_a) # 0
print(node_b) # 1
print(node_c) # 2
print(node_d) # 3
print(graph[node_a]) # my_node_a
print(graph[node_b]) # my_node_b
print(graph[node_c]) # 2
print(graph[node_d]) # ('a', 2)
edge_a_b = graph.add_edge(node_a, node_b, "edge_a_b")
edge_c_d = graph.add_edge(node_c, node_d, 100)
print(edge_a_b) # 0
print(edge_c_d) # 1
print(graph.edges()) # ['edge_a_b', 100]
このように、ノードやエッジへのアクセスに整数インデックスでアクセスしなければならない点が、NetworkXからrustworkxに乗り換えるのに必要な作業です。これらのインデックスはrustworkxのアルゴリズム内部でも用いられています。
import rustworkx as rx
graph = rx.PyDiGraph()
graph.extend_from_weighted_edge_list(
[
(0, 1, {"weight": 1}),
(0, 2, {"weight": 2}),
(1, 3, {"weight": 2}),
(3, 0, {"weight": 3}),
]
)
dist_matrix = rx.digraph_floyd_warshall_numpy(
graph, weight_fn=lambda edge: edge["weight"]
)
# [[ 0. 1. 2. 3.]
# [ 5. 0. 7. 2.]
# [inf inf 0. inf]
# [ 3. 4. 5. 0.]]
print(dist_matrix)
NetworkXグラフ \leftrightarrows
既存システムがすでにNetworkXが前提で書かれており、インターフェースは変えられない場合もありますよね。こういった場合には
- NetworkXグラフをrustworkxグラフに変換
- rustworkxグラフで高速に処理
- rustworkxグラフを再度NetworkXグラフに変換
のような手順を踏むことで、従来システムとの接続ができます。よって、以下のグラフ変換が有効活用できるかもしれません。
NetworkX \rightarrow
networkx_converter() を使えば実現できます。
import networkx as nx
import rustworkx as rx
graph = nx.DiGraph()
graph.add_node("node_a", value=1)
graph.add_node("node_b", value=2)
graph.add_edge("node_a", "node_b", weight=1)
rx_graph = rx.networkx_converter(graph)
# <rustworkx.PyDiGraph object at 0x101242d40>
print(rx_graph)
rustworkx \rightarrow
rustworkxのグラフをNetworkXのグラフに変換する関数は公式には存在しません。これはrustworkxをNetworkXに依存させなくするためです。ただ、以下のようにrustworkxグラフをNetworkXグラフに変換する関数は書けます。
import networkx as nx
import rustworkx as rx
def convert_rustworkx_to_networkx(graph):
"""Convert a rustworkx PyGraph or PyDiGraph to a networkx graph."""
edge_list = [(
graph[x[0]], graph[x[1]],
{'weight': x[2]}) for x in graph.weighted_edge_list()]
if isinstance(graph, rx.PyGraph):
if graph.multigraph:
return nx.MultiGraph(edge_list)
else:
return nx.Graph(edge_list)
else:
if graph.multigraph:
return nx.MultiDiGraph(edge_list)
else:
return nx.DiGraph(edge_list)
その他の機能
その他にも、matplotlibでグラフを描画するための機能(mpl_draw()、graphviz_draw())や、隣接行列をnumpy配列で返してくれるadjacency_matrix()があります。matplotlibでの描画機能が少なかったり、scipyのスパース行列で返す機能がなかったりで、NetworkXと比べると足りない機能も多いですが、これから順次拡充していくそうです。NetworkXにはあって、rustworkxにはない機能で、早く使いたいものがあれば、rustworkxリポジトリのissuesから “Enhancement request” issueをオープンすると、開発を優先するらしいです。
結び
本記事では、NetworkX、NetworKit、networkcそしてrustworkxのパフォーマンスを比較し、NetworKitとrustworkxの高速性を確認しました。そして、現在多くの現場で使われていると思われるNetworkXから、高速なrustworkxへの乗り換えに必要な情報をまとめました。
機能豊富で使いやすいNetworkXも良いライブラリですが、より高速なrustworkxという選択肢が広まる一助となれば幸いです[19]。
蛇足ですが、実は記事執筆当初、"NetworkX"を"networkx"という風にすべて小文字で書いていました。本家は"NetworkX"表記なので修正してよかったのですが[20]、"networkx"と"rustworkx"を書き並べると区別がつきにくくなって読み直すときに目が滑って苦労していました。NetworkXのNとXが大文字なおかげで、rustworkxと識別しやすくなってとても助かりました。しかしNetworkXにインスパイアされたrustworkxは何故全て小文字表記なんでしょうね？
お知らせ
少しでも弊社にご興味を持っていただけた方は、お気軽にご連絡頂けますと幸いです。まずはカジュアルにお話を、という形でも、副業を検討したいという形でも歓迎しています。
-
執筆執筆当時 ↩︎
-
cuGraphという、GPUを用いたかなり早そうなライブラリもありましたが、必ずしもGPUが使えるとは限らないので、今回の比較対象からは除いています。 ↩︎
-
RustやC言語はコンパイル型言語であり、プログラムの実行前にコンピュータが解釈できるように翻訳することで高速に動作させることができます。一方、Pythonをはじめとするインタプリタ型言語は、実行中にコンピュータが実行できるように逐次翻訳するので、コンパイル型言語に比べて実行が遅くなる傾向があります。 ↩︎
-
アルゴリズムを知っている人が多そうという理由で選定しました。 ↩︎
-
密度
D 0 \leq D \leq 1 V V^2 D DV^2 -
dijkstra方の実装が全て二分ヒープだったのは偶然です。実験する身としてはありがたかったです。 ↩︎
-
NetworKitのソースコードをみた感じ、並列化してそうでした。 また、実験中にCPU利用率が800％近くになっていたので間違いなしです。 ↩︎
-
もちろんコア数に依存します。 ↩︎
-
名前の由来はもちろん Rust + NetworkX = Rustworkx です。元々はretworkxと呼ばれていたらしいです。 ↩︎
-
drop-in replacement: 完全互換性を意味する言葉です。 ↩︎
-
記事執筆時点 ↩︎
-
これはPythonのlistなどのsequenceのイメージではなく、mappingです。これはノードやエッジがグラフから削除されるとsequenceでは都合が悪いからです。 ↩︎
-
それぞれ関数名にgraph_* and digraph_* のように接頭辞がついています。 ↩︎
-
ペイロードと言います。 ↩︎
-
記事執筆時点のバージョンは0.13.2です。 ↩︎
-
この記事での便宜的な呼び方です。 ↩︎
-
高速な処理が必要な場面ではそもそもPythonを使うなという指摘もあり得る話ですが、Pythonユーザの多さ、データ分析との親和性など、Pythonを使わなければならない場面は多いと思っています。 ↩︎
-
しっかり確認したつもりですが、もし本文のどこかに"networkx"表記が混ざっていたら、執筆当初の名残です。蛇足ついでに申し上げると、置換しようにも、URLやサンプルコード内に"networkx"が部分文字列として多数存在するため、自動置換ができなかったのです。 ↩︎
Discussion