『消えたデータ型を探して』にたくさんの反響をいただきました。以下では、その中でもとくに興味深かったものをいくつか紹介します。

ブログでの反応

• “消えた”グラフデータ型はすでに存在する。70年代に発明されていた ― Datalogについての記事です。

メールとコメント

引用部分はすべて原文のまま掲載しています。

GraphBLAS

はじめまして、Michel Pelletierと申します。GraphBLAS API標準とPythonバインディングのコントリビューターの一人です。

ブログがHacker Newsのフロントページに掲載されたこと、おめでとうございます。あなたの疑問に役立つかもしれない情報をHNに返信したのですが、大量の議論に埋もれてしまっています。メールでの連絡を歓迎されていると気づいたので、直接お送りすることにしました。

あなたが探しているグラフのデータ型は、すでに言及されている行列そのものです。ブログの中では隣接行列について触れられていますが、そこではグラフそのものではなく、単なる格納形式として扱われていました。しかし、グラフと行列は概念的にも代数的にも同型です。すべてのグラフ、ひいてはすべての複合データ構造は数学的には行列であり、すべての行列はグラフなのです。ハイパーグラフやマルチグラフは「接続行列（Incidence Matrix）」で表現されます。これは2つの長方形行列を使って、ノードからエッジ、エッジからノードへの隣接関係を表すものです。

MITリンカーン研究所スーパーコンピューティングセンター所長のJeremy Kepner博士を中心とする大勢の研究者グループによる、非常に優れた入門論文があります。

https://arxiv.org/pdf/1606.05790.pdf

グラフを行列として考える際のコンピュータ上の問題は、多くのグラフが疎（スパース）であるのに対し、多くの行列ライブラリ（たとえばNumPy）が密（デンス）であることです。そのため隣接行列を使うと非常にコストが高くなります。密な行列では、空間のほとんどがゼロで占められてしまうからです。これは極めて非効率で、フォン・ノイマンアーキテクチャに典型的なキャッシュ階層を活かせません。この2つの世界はまだ完全には融合していないのです。

しかし、効率的な疎行列計算、ひいては疎なグラフ解析の分野では、多くの研究開発が進められています。一見異なるものに見えますが、実際には両者は同じものです。行列乗算は、グラフ上の幅優先探索の1ステップに相当するのです。これも両者が同型であることの一部です。機械学習や人工知能の研究の多くは疎行列とグラフの両方を扱っており、両パラダイムの性能向上という点で研究は大きく統合されています。

この件でよく聞かれる大きな疑問は「なぜ」です。なぜノードやエッジをたどる関数を書くのではなく、線形代数の式を書くのか。その最も重要な答えの一つが、巨大なグラフに対する並列化です。グラフが本当に、数十億、数兆ものエッジを持つほど巨大になると、アルゴリズムの処理を効率的に分割する必要があります。どうやって分割するのでしょうか。エッジごとにforkしますか。スレッドプールを使いますか。どうやって作業をスケジューリングし、グラフを効率的に分割するのでしょうか。さらにそれをCUDA上でやるとなれば……最も優秀なプログラマーにとっても、ほぼ不可能な問題になります。

GraphBLASでは、グラフ操作は線形代数の式であり、一連の行列乗算に分解されます。Ax = bのような式を書くだけで、特定のターゲットアーキテクチャ上で最も効率的に処理を実行する方法を、基盤となるライブラリが判断してくれます。Chromebookでもスーパーコンピュータでも、コードは変わりません。変わるのは、より大きなグラフを扱えるマシンの能力だけです。GraphBLASは、基盤となるアーキテクチャだけでなく、与える問題の形状や種類に基づいて「JIT」コンパイルされる言語だと考えることができます。線形代数は数学、科学、工学の共通言語なので、この手法は既存の多くの研究に自然に応用できます。

とりあえずこの情報をお届けしたくご連絡しました。今後の探求がうまくいくことを祈っています。さらに詳しく知りたいことがあれば、いつでもお話しします。C API委員会のメンバーとして、このテーマを広めるのは私の仕事の一部でもあり、喜んで紹介させていただきます。

ありがとうございました！

Gremlin

このエッセイの初期の草稿では、ApacheのグラフコンピューティングフレームワークであるTinkerPopと、そのクエリ言語であるGremlinについて触れていました。最終版では削除したのですが、それが抜けていることに気づいた方が何人かいらっしゃいました。そのうちの一つの反応をご紹介します。

Cypherには触れていましたが、Neo4j/TinkerPop向けの表現力豊かなグラフクエリ言語であるGremlinについては触れていませんでした。

https://tinkerpop.apache.org/

これはShiftLeftに買収されたJoernというSASTツールで使われていたもので、金融業界でも広く使われていると思います。

私が最後に使ったのは、Maven上のすべてのソフトウェアパッケージとそれらの相互依存関係をグラフ化する際でした。

プログラミング言語へのバインディングもよくできています。私はPython用のGremlinを使ったので、馴染みのあるスクリプト言語から操作できました。デフォルトのREPL／スクリプトはGroovyなのですが、そちらはあまり得意ではないので。

Gremlinでグラフにクエリを投げる作業と、Pythonで通常の命令的なスクリプトを書く作業を相互に行き来し、その結果からさらにクエリを投げることができます。とても自然な使い心地でした。

グラフ全体を対象とするアルゴリズムがどの程度対応しているのかは分かりません。私は常に、中心性のようなグラフ全体の統計よりも、探索（トラバーサル）ベースのクエリに興味があったので。

ルービックキューブ

CodeProjectのニュースレターでリンクされていたことがきっかけで、グラフ用のソフトウェアライブラリが欠けているというあなたの記事を拝見しました。素晴らしい記事でした。記事を書く際に相談された方々のような高いレベルではありませんが、それでもグラフ用の汎用ソフトウェアライブラリを作ることの難しさについて、もう一つの例を提供できればと思います。私は、長年にわたってコンピュータを使ってルービックキューブの数学を研究してきた、とても非公式なグループの一員です。

ルービックキューブの背後にある数学は群論と呼ばれ、群でできることの一つに、ケーリーグラフと呼ばれるグラフを使って群を可視化することがあります。物知りのGoogleはそれを次のように説明しています。「ケーリーグラフは、群の構造をグラフの形で表現することで、群の抽象的な構造を容易に可視化するために頻繁に用いられます。群Gのサイズや生成元の数といった性質は、Gがケーリーグラフとして描かれることで、はるかに調べやすくなります。」具体的には、ルービックキューブの取りうるすべての配置はケーリーグラフ上のノードとして表すことができ、隣接するノードとはちょうど1手で到達できる配置同士のことです。記事の中で15パズルについて触れていらっしゃいましたが、実はルービックキューブの研究者の一人が、15パズルの完全で非常に高速なソルバーを書いています。そして、15パズルの規模は、ルービックキューブのケーリーグラフの規模に比べれば取るに足らないものだということも分かっています。

いずれにせよ、私は1985年からルービックキューブを研究するコードを書いてきました。これは単にルービックキューブを「解く」ためではなく、実際それ自体はとても簡単なことです。そうではなく、10^20に迫るすべての配置について、その配置を解くのに必要な最小の手数を求めるためです。この問題が未解決のままなのは、単純に規模があまりにも大きいからです。どのような配置も、1手を何と数えるかによって、20手あるいは26手で解けることが分かっています。しかしそれは、すべての可能な配置について、可能な限り少ない手数で解く解法を見つけることとは同じではありません。

いずれにせよ、私は多くの経験から、この問題に実用的な方法で取り組むためには、ルービックキューブに特化した独自のデータ構造を開発しなければならなかったことを知っています。核心的な問題は（ここであなたの記事から引用しますが）「パフォーマンスがあまりにも重要である」ということです。私が必要とすることをやってくれるライブラリは見つからなかったので、自分で作りました。

素晴らしい記事をありがとうございました、

Jerry

「20手あるいは26手」とは何を意味するのか、また使っているデータ構造について詳しく教えてもらえるか尋ねたところ、以下のような返事をいただきました。

ご推察のとおり、1回の半回転を1手と数えるか2手と数えるかが、1手を何と数えるかの代表的な例です。90度回転だけを1手と数える場合、それはクォーターターン計量と呼ばれます。この計量では、どの配置も26手以内で解くことができます。90度回転も半回転もともに1手と数える場合は、フェイスターン計量と呼ばれます。この計量では、どの配置も20手以内で解くことができます。しかし、1手を何と数えるかには他にも選び方があります。ルービックキューブはどの方向にも3つの層があります。通常は、天面や底面のような外側の層の動きだけを1手と数え、天面と底面の間の層や、右面や左面の間の層といった中間層は数えません。しかし、中間層の動きを1手と数えることも、時には興味深いことです。別のバリエーションとして、1つの軸が固まっていると仮定する「固まった軸（stuck axle）」問題があります。たとえば、天面は動かさず、キューブの他の5つの面の層だけを動かすといったものです。このバリエーションでもすべての配置に到達できますが、ケーリーグラフはどの軸も固まっていない場合と同じ対称性を持ちません。また、固まった軸のあるキューブを解くには、標準的な20手や26手よりもはるかに多くの手数が必要になることがあります。

ルービックキューブのための標準的なデータ構造があるとは思いません。キューブに取り組んでいる人はそれぞれ独自のものを持っています。ただし、キューブを忠実に表現するデータ構造は、キューブを忠実に表現する他のデータ構造と、ある意味で同型でなければならないという自明な意味はあります。大きな違いは、データ構造が配置だけからなるのか、それとも配置と手の両方からなるのかという点です。たとえば、前面を時計回りに90度回転させる動きを2回続けることは、前面を反時計回りに90度回転させる動きを2回続けることと同じ配置になります。ケーリーグラフでは、これらの手の並びは、続けていくとループになります。このループは4手のサイクル（4-cycle）です。では、手と配置を保存するのか、それとも配置だけを保存するのか。

他の人がこれらの問題をどうデータ構造で扱っているのか、正直よく分かりません。私自身はケーリーグラフ全体を明示的に保存してはいません。その代わりに、配置を保存し、各配置について、その配置から可能な各手について、その手が解けた状態から遠ざかるのか近づくのかを示す1ビットを保存しています。クォーターターン計量では各配置につき12ビット、フェイスターン計量では各配置につき18ビットあります。これらのビットが暗黙のうちにケーリーグラフを定義していますが、グラフ自体を明示的に保存しているわけではありません。この問題に取り組んでいる他の人たちは、正準的な手の並びを使うことについて話しています。たとえば、前面を時計回りに2回続けて回すことはできても、前面を反時計回りに2回続けて回すことはできない、といったものです。私はビットを使って、それと似て非なることをしています。

もう一つの問題は、木構造が必要だったことです。木はグラフの特殊な場合と考えることができます。つまり、木とは、あるノードが根（ルート）として宣言され、グラフの中にループがないグラフのことです。私は独自の木構造を作らなければなりませんでした。必要だった木構造は次のようにして生じます。標準的なルービックキューブには54個の色付きシールがあります。標準的な数学モデルでは、各面の中央のシールは動かないので、動くシールは48個残ります。48個のうち、24個は3×3の各面の角にあり、24個は3×3の各面の辺にあります。角のシールと辺のシールは互いに重ならないので、私は各角のシールをAからXまでの文字で、各辺のシールをAからXまでの文字でラベル付けして、キューブの配置を表現しています。各配置は、24文字からなる単語の順序対となり、各単語の中で各文字はちょうど1回だけ現れます。

では、なぜ木が必要なのでしょうか。私はこれらの単語を非常に高速に見つけられる必要があるからです。スペルチェック辞書で単語を非常に高速に見つけるようなものです。名目上、木の中の各ノードは、木の中の他のノードへの24個のポインタを必要とします。しかし、実際のスペルチェック辞書の現実の単語とは異なり、各文字は各単語の中で1回しか現れません。そのため、木の葉ノードに近づくにつれて、各ノードはほとんどがヌルポインタで占められることになり、非常に貴重なメモリの莫大な無駄になります。そこで私は、高速な検索のために配置の保存に対応した木構造を作らなければなりませんでした。標準的なライブラリのルーチンは、速度もメモリ効率も十分ではありませんでした。

つまり本質的に、私は2つのデータ構造を重ね合わせています。一つはビットスイッチを使ってキューブのケーリーグラフを定義するもので、もう一つはスペルチェック辞書のような木を使って特定の配置を非常に高速に見つけるものです。そして木はグラフの特殊な場合にすぎません。

これで疑問にお答えできたか分かりませんが、お役に立てば幸いです。

Jerry

グラフとナレッジデータベース

Hillelさん ― 明確な勝者がいない理由を分かりやすく説明しながら、グラフ表現についての探求を共有していただきありがとうございます。あなたが挙げている問題は、実行可能な代替案を妨げるほど大きなものではないのではないかと思っています。

私はまずSmalltalkプログラマーとして、次にWikiの作者としてこの問題に取り組んでいます。どちらも、少しずつ組み立てられ、使い続ける中で永続化される、グラフのような構造を持っています。私の最新のWiki実装を取り巻く小さなコミュニティでは、段落、画像、アウトライン、表と並んで、ページにグラフを追加したいという強い要望があります。私たちはDotをマークアップとして使ったGraphvizでこれに部分的に対応してきました。しかし、これではyamlやcsvのファイルで得られるような計算や共有ができません。

最近では、（たとえばJavaScriptで）グラフを、ノードと関係（relation）の配列を持つオブジェクトとして表現するやり方を採用しています。空のグラフは次のようになります。

{nodes:[], rels:[]}

ノードと関係はそれぞれ、型を示す文字列と、プロパティのための追加のオブジェクト、そしてそれらを結びつける管理されたインデックスを持つオブジェクトです。これはその後、（ループのない）JSONに便利にシリアライズでき、広く普及した形式であり、キロバイト単位で測られるグラフには十分です。

これらのグラフは、私たちが豊富な経験を持つNeo4jのオブジェクトへ容易に変換できます。より多くの場合、Wiki自体を超えてデータベースを維持することは避けています。ささやかなCypherインタプリタも作りましたが、それはあまり有用だとは分かっていません。私たちは驚くべき発見をしました。1つの大きなNeo4jグラフを構築してそこから同じ問題を解くのに必要なグラフをクエリで取り出すよりも、多くの小さなグラフをマージして当面の問題を解くグラフを作ることの方が多いのです。

最近では、問題空間の分野横断的な関心事に基づいて、問題を「アスペクト」に分割するようになりました。数十、あるいは数百ものこうしたグラフを持つこともあります。私たちはこれらをWikiをブラウズするようにブラウズします。Wikiリンクに相当するものは、まだ取り込まれていないグラフの中に同じノードが現れることを認識することから生まれます。これは「推薦（recommending）」のプロセスであり、クエリは、ブラウザ上でGraphvizを実行して作業中のものを即座に描画しながら、推薦を選んだり外したりすることに置き換えられます。

このメールの冒頭では、私たちのグラフ抽象化についてより完全な説明を書いていたのですが、あなたが私たちの経験を面白いと思ってくださるか分からなかったので控えました。コミュニティ内のコラボレーション問題を伴うような、この手法が有用だったアプリケーションについても説明できます。

もし何か関心が重なる部分があると思われましたら、ぜひやり取りできれば嬉しいです。

ありがとうございます、よろしくお願いいたします ― Ward

このためのコードはこちらで公開されており、ドキュメントやサンプルも併せてご覧いただけます。続報のメールです。

Hillelさん ― 私たちは、より大きな問題のアスペクトを表す小さなグラフを探しています。European Patternsカンファレンスに提出される論文を読むよう頼まれた際、私はそれを非常に注意深く読み、パターンの中のすべての「関係的」な文をマッピングすることにしました。アスペクト間の予期せぬ重なりが黄色で示されているのがこちらの画像です。

この特定のグラフビューアは紆余曲折を経てきました。Wikiページ上のスクリプトとして始まり、オンラインコラボレーションのためにCroquet上で動くスタンドアロンのウェブアプリとして切り出され、そしてここではWikiに戻る単独ユーザー向けの「ソロ」アプリケーションとなっています。まだ自明なものではありません。しかし、同じような探求に関心を持つ共同レビュアーと連携したWikiページの最後の段落にある「open」リンクから起動できます。http://ward.dojo.fed.wiki/aspects-of-pattern-relations.html

異なる「アスペクト」の可能性を示す、さらに2つの似たプロジェクトがあります。1年分のRecent Changesを切り刻むプロジェクトと、検索エンジンのソースコードにノード・関係コメントでアノテーションを付け、GitHub Actionsでそれらをグラフファイルに抽出するプロジェクトです。