消えたデータ型を探して
原文は Hillel Wayne により に公開されました。 このブログを購読する
（有向）グラフとは、矢印（エッジ）で結ばれたノードの集合のことだ。ノードやエッジにはデータを載せることもできる。いくつか例を挙げよう。
グラフはソフトウェアエンジニアリングのあらゆるところに存在する。
- パッケージの依存関係は有向グラフをなし、モジュールの import も同様だ。
- インターネットは、ウェブページ間のリンクからなるグラフだ。
- モデル検査器は、取りうるすべての設定からなる「状態空間」を探索することでソフトウェアを解析する。ノードが状態、エッジが状態間の正当な遷移に対応する。
- リレーショナルデータベースは、レコードをノード、外部キーをエッジとするグラフだ。
- グラフは、連結リストや二分木、ハッシュテーブルを一般化したものだ。1
グラフはビジネスロジックにもあふれている。参考文献付きのホワイトペーパーは引用のグラフをなす。交通網は経路のグラフだ。ソーシャルネットワークはつながりのグラフだ。ソフトウェア開発を長くやっていれば、どこかで必ずグラフに遭遇する。
私はあらゆる場所にグラフを見出し、あらゆる種類のシステムの分析にグラフを使っている。一方で、実際にコードでグラフを使うのは気が重い。主流の言語でグラフをまともにサポートしているものはほとんどない。組み込み型として持っている言語は一つもなく、標準ライブラリにある言語もごくわずかで、エコシステムに堅牢なサードパーティ製ライブラリがある言語すら多くない。たいていは自分でグラフを一から作らなければならない。ソフトウェアエンジニアがグラフを使える場面の多さと、プログラミング言語のエコシステムがグラフをサポートしていないことの間には大きな隔たりがある。グラフ型はどこに行ってしまったのか。
仕事でグラフに遭遇する機会が増えるにつれ、この疑問はますます気になるものになっていった。そこで昨年末、ようやく答えを探し始めた。私のニュースレターで呼びかけを行い、関連する専門知識を持つ人——グラフアルゴリズムの考案者、言語委員会のメンバー、グラフライブラリのメンテナー——に連絡を求めた。十数人にインタビューするつもりだったが、結局4人に話を聞いただけで十分だった。
- Zayenz：Gecode 制約ソルバーの元コア開発者で、「存在するあらゆるグラフアルゴリズムを実装した」人物
- Bradford：Nosey Parker セキュリティライブラリの作者で、いくつもの新しいグラフアルゴリズムの考案者
- Nicole：元グラフデータベースエンジニア
- Kelly：Pythonのグラフライブラリ NetworkX のメンテナーであり、コンパイラ開発者
この4人がいずれも似たような答えを返してきたので、インタビューを切り上げて執筆を始めた。
理由
設計上の選択肢が多すぎる
ここまで説明してきたのは有向グラフだ。これとは別に、エッジに向きがない無向グラフもある。有向・無向のどちらのグラフも、2つのノード間に張れるエッジが最大1本の単純グラフか、複数本張れる多重グラフかに分かれる。さらに、それぞれのタイプについて、1本のエッジが3つ以上のノードを結ぶハイパーグラフや、エッジが別のエッジを指すことができるウーバーグラフといったバリエーションもある。考えられるすべてのバリエーションについて、さらに決めなければならないことがある。IDを付けるのはノードだけか、エッジにも付けるのか。ノードにはどんなデータを、エッジにはどんなデータを持たせられるのか。ライブラリが決めなければならないことは山ほどある。
しかし、これらの区別はそもそも重要なのだろうか。単純グラフは多重グラフの退化したケースにすぎないし、無向エッジは2本の有向エッジにロスなく変換できる。言語側が有向ハイパーウーバー多重グラフだけを提供して、ユーザーが好きなように制限できるようにすればいいのではないか。
これには2つの問題がある。まず、インターフェースが変わってしまう。たとえば、ある操作が単一の値を返すのかリストを返すのかが違ってくる。次に、後で詳しく述べるが、グラフアルゴリズムの性能は極めて重要であり、特殊ケースが本当に大きな意味を持つ。Kellyは最大重みマッチングの例を挙げた。グラフが「二部グラフ」だとわかっていれば、マッチングを見つけるのに特定の高速なアルゴリズムを使えるが、そうでないグラフでは遅く汎用的なアルゴリズムを使わなければならない。
結局は「アルゴリズムのディスパッチ問題」に帰着します。問題P、グラフG、そしてG上でPを解くアルゴリズムA、B、Cがあるとき……どれを実行すべきか。Gが二部グラフかどうかわからず、アルゴリズムCは二部グラフでしか動かないとしたら、Gが二部グラフかどうかを判定するのにどれだけ時間をかけられるか、ということです。 — Kelly
理想的なグラフライブラリは、さまざまな種類のグラフをサポートするだろう。しかし、それはグラフで何をするかをサポートする時間を奪うことになる。グラフアルゴリズムを正しく実装するのは悪名高いほど難しい。あるエッセイで、Pythonの生みの親は自作の find_shortest_path アルゴリズムを実装している。それは5回も修正を重ねなければならなかった。
私が比較した pagerank の実装は、すべて間違っていました。 — Nicole
では、ライブラリにはどのアルゴリズムを含めるべきなのか。「人々がグラフでやりたいことの量は馬鹿げたほど多い」とKellyは語った。それは私自身の経験とも、インタビューした全員の経験とも一致する。グラフは強力すぎるがゆえに、その可能性のすべてが理解を超えているようにさえ思える。「問題は、どこで線を引くか、ということです」とKellyは言った。
NetworkXにとって「線」は、約500種類の異なるグラフアルゴリズムであり、それだけで約60,000行のコードになる。比較のために挙げると、300のパッケージからなるPython標準ライブラリ全体で60万行弱だ。2
そう考えると、標準ライブラリにグラフが見当たらないのも当然だ。言語のメンテナーは、どの種類のグラフをサポートするか、どのトポロジーを特別扱いするか、どのアルゴリズムを含めるかを決めなければならない。こうしたメンテナンス作業をサードパーティに任せるのは理にかなっている。これは言語開発における主流のトレンドでもある。「batteries included（電池付属）」で知られるPythonでさえ、20個の電池を取り除こうとしている。
サードパーティなら、グラフをどう設計し、どのアルゴリズムを含めるかについて、思い切った決断を下すことができる。しかし次に直面するのが次の問題だ。グラフのインターフェースが決まったとして、それをどう表現するのか。
実装上の選択肢が多すぎる
ごく単純な単純有向グラフだけをサポートするとしよう。ノードには同一性があり、エッジにはなく、どちらにも付随するデータはない。このグラフをどうエンコードするか。
プログラミング言語が内部でこれを格納しうる方法は、たとえば次の4つだ。
- エッジリスト:
[[a, b], [b, c], [c, a], [c, b]] - 隣接リスト:
[[b], [c], [a, b]] - 隣接行列:
[0 1 0; 0 0 1; 1 1 0] - 相互に参照し合う3つの構造体の集合
表現方法が違えば、グラフ操作の性能特性も違ってくる。100ノード、200エッジの有向グラフを考えてみよう。隣接行列表現を使うと、200個の1と9,800個の0を含む100×100の行列が必要になる。一方、エッジリストを使えば、必要なのは200組のノードのペアだけだ。プログラミング言語や最適化の度合いにもよるが、メモリ使用量に20倍以上の差が出ることもある。
今度は100ノード、8,000エッジのグラフで、ノード0と93の間にエッジがあるかどうかを調べる場合を考えてみよう。行列表現なら graph[0][93] でO(1)のルックアップだ。エッジリスト表現なら、8,000本のエッジすべてを走査するO(|edge|)の操作になる。3
エッジが少ないグラフは疎、ほとんどすべてのエッジがあるグラフは密と呼ばれる。同じプログラムの中でも、両方の種類のトポロジーに対して両方の操作が必要になることがある。外部データからグラフを構築する場合、最初は疎だったグラフが後で密になることもある。内部のグラフ表現について「これが良い」という選択肢は存在しないのだ。
しかも、これは最も単純な有向グラフだけの話だ。ノードのデータはどう実装するのか。エッジのデータは。異なる種類のノードやエッジは。サードパーティ製ライブラリの多くは、大きく分けて次のどちらかに当てはまる。
すべてのユースケースをカバーする単一の豊富なデータ型を、効率を犠牲にして提供する。NetworkXはグラフを辞書の辞書の辞書として格納しており、これによりノードとエッジの両方が任意のデータを持てるようになっている。4
表現ごとに別々のグラフ型を提供し、ノードやエッジのデータはグラフ型とは別に保存することをユーザーに委ねる。
後者の例が、Rustで最も人気のあるグラフライブラリである Petgraph だ。Petgraphには用途別に graph、graphmap、matrix_graph がある。Bradfordは、gitリポジトリの全履歴にわたってシークレットをスキャンするセキュリティツール Nosey Parker でPetgraphを使った。彼がベンチマークに使ったのはCPythonで、25万コミットと130万オブジェクトがある一方で、コミットノードあたりのエッジは数本しかない。彼は隣接リストを選んだ。
多くの表現をサポートすることには大きな欠点がある。アルゴリズムを追加する際の作業が何倍にも増えるのだ。グラフ表現ごとにアルゴリズムを別々に書けば、メンテナンスの負担は3倍、4倍になる。代わりにポリモーフィックな型に対する汎用的な抽象化を書けば、ライブラリの性能は落ちる。手書きのグラフアルゴリズムは汎用的なアルゴリズムより20倍以上速くなることもある、と見積もるプログラマーもいた。
そして、これはインタビューした全員が口にした最大の不満へとつながる。
性能があまりにも重要だ
「汎用的な」グラフ実装では、たいてい役に立ちません。 — Bradford
これが最大のポイントだ。
多くのグラフアルゴリズムはNP完全か、それ以上に難しい。5 NP完全は大規模な問題でもしばしば扱いやすいが、グラフはとてつもなく巨大な問題になりうる。表現の選択は、それをどれだけ速く解けるかに大きく関わってくるし、アルゴリズム実装の細部も同様だ。
話を聞いた全員が、この手の逸話を持っていた。Nosey Parkerでは、Bradfordは各コミットについてファイルシステムのスナップショットを再構築する必要があり、そのためにオブジェクトグラフを走査しなければならなかった。提供されている4つのグラフウォーカーは、どれも彼のユースケースではスケールしなかった。代わりに彼は、その場で「半ば新しい」グラフ走査アルゴリズムを設計しなければならず、それによってメモリ使用量を1000分の1に削減した。
[petgraph]ですぐに動くプロトタイプは作れました。でも……性能の制約が現実とぶつかる、まさにそういうケースでした。 — Bradford
Zayenzは別の問題を提起した。グラフが単純に大きすぎて扱えない場合はどうするのか。彼は15パズルの解を見つける例を挙げた。これは状態空間上で A*探索を実行することで行われる。200兆を超える状態からなる状態空間だ。
すべてのノードを生成してしまったら、もう負けです。 — Zayenz
Zayenzは、Gecode制約ソルバーにグラフを追加するある研究プロジェクトを監督した。彼らは最終的に、汎用的なグラフ型では問題ごとに表現を手で選ぶやり方に太刀打ちできないことを悟った。
複雑なグラフアルゴリズムを実行すること自体を目的として設計されたグラフデータベースでさえ、この問題に苦しんでいる。グラフデータベースエンジニアだったNicoleは、基本的なグラフ操作を最適化する際の課題について語ってくれた。
走査を行うときは、深さを制限するか、グラフ全体を訪問することを受け入れるかのどちらかです。「ここから3ステップ先まで行って、パスが存在するか探す」といった深さ探索をすると、かなりの量のデータを訪問することになります。 — Nicole
その仕事を辞めた後、彼女はグラフクエリの性能コンサルタントとして働いた。それは多くの場合、グラフデータベースからの移行を意味した。彼女はあるプロジェクトについて語ってくれた。グラフクエリを高速化するために、1つの計算はそのまま残し、残りはMapReduceの手続きとして書き直したのだ。「理解するのはずっと難しくなりました」と彼女は言った。「でも、一晩で終わるようになったんです」
こうしたことすべてが意味するのは、解きたいグラフ問題があるなら、データ表現やアルゴリズムの細部を大幅に制御する必要があるということだ。性能を少しでも無駄にする余裕はないのだ。
全員の意見は一致した
というわけで、グラフのサポートが広まらない理由はこうだ。
- グラフには多くの種類がある
- それぞれの種類のグラフに多くの表現方法がある
- グラフアルゴリズムは数多く存在する
- グラフアルゴリズムの性能は、グラフの表現や実装の詳細に非常に敏感だ
- 人々は非常に大きなグラフに対して非常に高コストなアルゴリズムを実行している
これで、なぜ言語が標準ライブラリでグラフをサポートしないのかがわかる。設計上の決定が多すぎ、トレードオフが多すぎ、メンテナンスの負担が大きすぎるのだ。プログラマーがサードパーティのグラフライブラリを避ける理由もわかる。制限が多すぎるか、遅すぎるかのどちらかだからだ。そして、プログラマーが極端な状況を除いてグラフという観点で物事を考えたがらない理由もわかる。扱うのが難しすぎるのだ。
この調査を始めてから、仕事でいくつもの新しいグラフ問題に遭遇した。相変わらず、システムをグラフとして分析することには価値を感じつつ、実装するのは気が重い。ただ、今では他のみんなも同じように気が重い理由がわかった。読んでいただきありがとう！
Predrag Gruevski 氏には調査協力を、Lars Hupel 氏、Predrag Gruevski 氏、Dan Luu 氏、Marianne Bellotti 氏にはフィードバックをいただいた。また、インタビューに応じてくれたすべての方々に感謝する。この記事が気に入ったら、ぜひ ニュースレターに参加してほしい。毎週新しいエッセイを書いている。
私は企業向けに形式手法のトレーニングを行い、ソフトウェア開発をより速く、より安く、より安全にしている。詳しくはこちらをご覧いただきたい。
付録：グラフ型を持つ言語
グラフクエリ言語
グラフクエリ言語（GQL）6は、グラフデータベースにとって、SQLがリレーショナルデータベースに対するものと同じ位置づけだ。広く使われている標準はないが、最も人気のあるものの2つは、RDFトリプルをクエリするための SPARQL と、Neo4jの Cypher だ。皮肉なことに、GraphQL はグラフクエリ言語ではない。その名前は Facebook Graph Search に由来している。私はグラフデータベース自体はプログラミング言語におけるグラフとはほぼ別物と考えていたが、そのクエリ言語は、グラフがプログラミング言語でどう機能しうるかを示している。
すべてのGQLとSQLの主な違いは、「結合」（リレーションシップ）が第一級の存在であることだ。映画と人物のデータセットがあり、人物が映画に出演したり、監督したり、プロデュースしたりするとしよう。SQLでは各リレーションシップを多対多のテーブルとして実装するため、「映画Xに出演したのは誰か」をクエリするのは簡単だが、「映画Yに何らかの役割で関わったのは誰で、その役割は何だったか」をクエリするのは難しい。SPARQLではリレーションシップは単なるエッジなので、同じクエリが簡単に書ける。
PREFIX mv: <your_movie_ontology_URL>
SELECT ?person ?role
WHERE {
?person ?role mv:casablanca.
}Cypherも同様の仕組みを持っている。GQLではエッジを操作することもできる。反転させたり、合成したり、推移閉包を取ったりといった具合だ。ケヴィン・ベーコンから何段階か離れたすべての俳優を見つけたいなら、次のように書ける。
PREFIX mv: <your_movie_ontology_URL>
SELECT ?a
WHERE {
mv:kbacon (:acted_in/^:acted_in)+ ?a.
# a/b = join two lookups
# ^a = reverse a
# a+ = transitive closure
}SPARQLではパスの長さを取得したり、2人の俳優を結ぶ映画の連鎖を収集するといった、パスに沿った計算を行ったりすることはできない。これをサポートするGQLは、かなり複雑になる。
私がGQLを見て得た主な教訓は、グラフをサポートするプログラミング言語が提供すべき、有用な走査プリミティブの集合があるということだ。興味深いことに、形式仕様言語である Alloy は、その「リレーション」データ型に対してこれらのプリミティブをすべて備えている。そのため、Alloyでグラフ表現を扱う方が、普通のプログラミング言語で扱うよりもずっと楽だと感じている。とはいえ、これらはすべてラベル付きエッジで機能するものであり、他のグラフ表現ではうまくいかないかもしれない。
標準ライブラリにグラフを持つ主流言語
Python は2020年に graphlib を追加した。ここでの議論によれば、トポロジカルソートは「基本的なアルゴリズム」であり、「MRO（メソッド解決順序）ロジックの純粋なPython実装」に役立つからというのが理由だった。graphlibには TopologicalSorter 以外のメソッドはなく、ノード辞書として表されたグラフしか受け付けない。異例なことに、ノード辞書の向きは逆になっている。グラフ a -> b は {b: [a]} として表される。
2023年時点で、CPythonの中でgraphlibを使っているものは何もなく、GitHub上でgraphlibを参照しているファイルは900件にも満たない。比較すると、同じく2020年に追加された別のパッケージである zoneinfo は6,000件以上のファイルに現れ、def topological_sort( という文字列は4,000件に現れる。これらの多くは2020年以前のものだろうが、ざっと見た限り、これらの自作トポロジカルソートはどれもgraphlibとは異なるグラフ表現を取っており、いずれにせよ置き換えはできない。やはりグラフの表現は重要だ。
他にグラフ型を持つ言語として私が見つけたのは、Erlang と SWI-Prolog の2つだ。どちらの言語にも詳しくないので、いつ追加されたのかはわからない。少なくともErlangについては2008年以前だ。Erlangのコア言語委員会のメンバーに連絡を取ったが、返事はなかった。
グラフ言語
bashではすべてが文字列、Lispではすべてがリストであるのと同じように、「すべてがグラフ」であるプログラミング言語だ。例としては GP2 や Grape などがある。分野の人々とのやり取りに基づくと、現時点ではこれはまだ非常にアカデミックな領域だ。
数理ソフトウェア言語
Mathematica、MATLAB、Mapleなどは、いずれも何らかの形でグラフライブラリを持っている。詳しく調べるために何千ドルものライセンス料を払う気にはなれない。
更新 2024-03-18
この投稿に寄せられたコメントをこちらにまとめた。
- いや、本当だ。ハッシュテーブルは二部グラフなのだ。これはクックー・ハッシングの操作の性能証明に使われた。 [return]
- 両方の計算は cloc 1.96 で導き出した。
networkx/networkx/algorithms（56989行）とcpython/Lib（588167行）で cloc を実行した。NetworkXライブラリ全体では約90,000行だ。 [return] - エッジリストをソートしておき、二分探索で
O(log(|e|))にすることで、より効率的にすることもできるが、その代わりエッジの挿入が高コストになる。 [return] - NetworkXにはグラフを別の表現に変換する関数はあるが、それらの表現を直接扱うための機能はない。 [return]
- 21の典型的なNP完全問題のうち、14がグラフ問題だ。 [return]
- 開発中のGQL標準として提案されている GQL 言語と混同しないように。 [return]
コメント
ログインしてコメントする