失われたデータ型を追う追跡

 (hillelwayne.com)
2 ポイント 投稿者 GN⁺ 2024-03-05 | 1件のコメント | WhatsAppで共有
  • グラフは依存関係、Webリンク、モデルチェッカーの状態空間、リレーショナルDBの外部キーのようにソフトウェアの至る所に存在するが、主流のプログラミング言語では組み込み型や標準ライブラリのサポートがほとんどない
  • 組み込みグラフ型を作るのが難しい第一の理由は、有向・無向、単純・マルチ、ハイパーグラフのようにグラフの種類が多く、特定の性質がアルゴリズム選択と性能を大きく左右するためである
  • エッジリスト、隣接リスト、隣接行列、参照し合う構造体など表現方式ごとにメモリ使用量と参照性能が異なるため、1つの汎用表現であらゆるユースケースを満たすのは難しい
  • グラフアルゴリズムは実装が難しく大きな入力で実行されることが多いため、Nosey ParkerやGecodeの事例のように問題に特化した表現と走査が汎用ライブラリより重要になることがある
  • 標準ライブラリにグラフが少ないのは、型・表現・アルゴリズム・性能のトレードオフと保守負担が大きいためであり、サードパーティライブラリも制約が多かったり遅かったりすることがある

グラフはありふれているが言語サポートは乏しい

  • グラフはノードとエッジで構成され、ノードとエッジにはデータを持たせられる
  • ソフトウェアエンジニアリングではグラフはさまざまな形で現れる
    • パッケージ依存関係とモジュールの import は有向グラフを成す
    • インターネットはWebページ間のリンクグラフである
    • モデルチェッカーは可能なすべての設定の状態空間を探索し、ノードは状態、エッジは有効な遷移である
    • リレーショナルデータベースはレコードをノード、外部キーをエッジとみなせる
    • グラフは連結リスト、二分木、ハッシュテーブルの一般化とみなせる
  • ビジネスロジックでも論文の引用関係、交通網の経路、ソーシャルネットワークのつながりのようなグラフが頻繁に現れる
  • グラフはしばしば必要になるが、主流言語の多くはグラフを組み込み型として提供せず、標準ライブラリに含めている例もまれである
  • 多くのエコシステムでは堅牢なサードパーティのグラフライブラリも不足しており、自前で実装しなければならないことが多い

グラフ型の設計には選択肢が多すぎる

  • グラフには有向グラフと無向グラフのほかにもさまざまな派生形がある
    • 2つのノード間にエッジが最大1本の単純グラフと、複数のエッジを許すマルチグラフ
    • 1本のエッジが3つ以上のノードを結ぶハイパーグラフ
    • エッジが他のエッジを指せるウーバーグラフ
  • 各派生形ごとに追加の設計判断が必要になる
    • エッジにもIDを付けるか、ノードにだけ付けるかを決める必要がある
    • ノードとエッジにどんなデータを保存するかも決めなければならない
  • すべてのグラフを「有向ハイパーウーバーマルチグラフ」のような汎用型で提供し、利用者側に制約させることもできるが、すぐに2つの問題が生じる
    • 演算結果が単一値なのかリストなのかといったインターフェースが変わる
    • 特殊なグラフ性質を活用できなければアルゴリズム性能が悪化する
  • 例えば maximum weight matching は、グラフが二部グラフだと分かっていれば高速なアルゴリズムを使えるが、一般グラフにはより遅く汎用的なアルゴリズムが必要になる
  • ある問題P、グラフG、アルゴリズムA・B・Cがあるとき、どのアルゴリズムを実行するかを選ぶアルゴリズムディスパッチの問題も生じる
  • 完璧なグラフライブラリは多くのグラフ種類をサポートしなければならないが、そのぶん実際に利用者が欲しいアルゴリズム実装に割ける時間は減る
  • グラフアルゴリズムは実装難度が高い
    • Pythonの作者が書いた find_shortest_path アルゴリズムはその後5回修正された
    • Nicoleは比較したPageRank実装はどれも間違っていたと述べている
    • NetworkX は約500個のグラフアルゴリズムを提供しており、アルゴリズムのコードだけでほぼ60,000行に達する
    • Python標準ライブラリ全体でも約300パッケージ、600,000行未満である
  • 標準ライブラリの管理者は、どのグラフ型、どのトポロジー特化処理、どのアルゴリズムを含めるかを決めなければならず、保守負担が大きい
  • Pythonも “batteries included” で知られているが、PEP 594 により20個の標準ライブラリモジュールを削除する流れにある

グラフの表現方式も1つに決めにくい

  • 最も単純な有向グラフだけを考えても、内部表現にはいくつもの選択肢がある
    • エッジリスト: [[a, b], [b, c], [c, a], [c, b]]
    • 隣接リスト: [[b], [c], [a, b]]
    • 隣接行列: [0 1 0; 0 0 1; 1 1 0]
    • 相互参照する構造体の集合
  • 表現方式によって演算性能は変わる
    • ノード100個、エッジ200本のグラフを隣接行列で表すと、100×100行列のうち1は200個、0は9,800個入る
    • 同じグラフをエッジリストで表すならノード対200個だけで済む
    • 言語と最適化水準によってはメモリ差が20倍以上になることもある
  • 逆にノード100個、エッジ8,000本のグラフでノード0と93の間のエッジを探す場合は結果が変わる
    • 隣接行列は graph[0][93] で O(1) の参照が可能である
    • エッジリストは8,000本のエッジを走査しなければならないため O(|edge|) 時間がかかる
  • エッジが少ないグラフは疎グラフ、ほぼすべてのエッジがあるグラフは密グラフである
  • 外部データからグラフを構築するプログラムでは、最初は疎グラフでも後で密グラフになることがあり、内部表現に「常によい選択」はない
  • ノードデータ、エッジデータ、複数種類のノードとエッジをサポートすると実装の複雑さはさらに増す
  • サードパーティライブラリは概して次のどちらかを選ぶ
    • すべてのユースケースを包含する機能豊富な単一型を提供する代わりに効率を犠牲にする
    • 表現方式ごとのグラフ型を別々に提供し、ノード・エッジデータ管理は利用者に委ねる

NetworkXとPetgraphが示すトレードオフ

  • NetworkXはノードとエッジに任意のデータを付けられるよう、グラフを dict の dict の dict 構造で保存する
  • 別表現へ変換する関数は提供するが、その表現自体を直接扱う方式は提供していない
  • Rustの代表的なグラフライブラリ Petgraph は、graph、graphmap、matrix_graph のようにユースケース別の型を提供する
  • Bradfordはgitリポジトリの全履歴からsecretを探すセキュリティツール Nosey Parker でPetgraphを使っている
    • ベンチマーク対象のグラフはCPythonで、250,000個のcommitと1,300,000個のobjectを含む
    • commitノードごとのエッジは数本しかないため隣接リストを選んだ
  • 複数表現をサポートするとアルゴリズム追加コストが大きくなる
    • 表現ごとに別々のアルゴリズムを書くと保守負担は3〜4倍に増える
    • 多相型の上に汎用抽象化を書けば性能は低下する
  • あるインタビュー回答者は、自作のグラフアルゴリズムが汎用アルゴリズムより20倍以上速いこともあり得ると見積もっている

性能制約こそがグラフライブラリの核心的問題である

  • グラフアルゴリズムにはNP-completeやそれ以上に難しい問題が多い
    • Karpの21個のcanonical NP-complete問題のうち14個がグラフ問題である
  • グラフ問題は非常に大きな入力で実行されることがあり、表現方式と実装の細部が実行可能性を左右する
  • BradfordはNosey Parkerで各commitごとにファイルシステムスナップショットを再構成するため、object graphを走査しなければならなかった
    • Petgraphの4種類のグラフwalkerはそのユースケース向けに拡張できなかった
    • そこで即席の “semi-novel” な graph traversal algorithm を設計し、メモリ使用量を1,000分の1に削減した
  • Zayenzは、グラフが大きすぎて全体を扱えない例として 15 puzzle を挙げる
    • 解法探索は状態空間で A* search を実行する形になる
    • 状態空間は20兆個を超える状態を持つ
    • 全ノードを生成した時点で、すでに失敗したも同然である
  • Zayenzが関わったGecode制約ソルバーへのグラフ追加研究プロジェクトでも、汎用グラフ型は問題に合わせた表現選択に太刀打ちできなかった
  • グラフデータベースも複雑なグラフアルゴリズム実行のために設計されているが、性能問題は残っている
    • Nicoleによれば、走査時に深さ制限を設けないとグラフ全体を訪れてしまう
    • 「3ステップ先までに行ってパスがあれば見つける」のような深さ探索でも大量のデータを訪れることになる
  • Nicoleはグラフクエリ性能コンサルティングで、主にグラフデータベースからの移行を手掛けている
    • あるプロジェクトでは1つの計算だけを残し、残りはMapReduce手順として書き直した
    • 理解しづらくはなったが、一晩のうちに実際に完了できるようになった

なぜ標準ライブラリにグラフが少ないのか

  • 広範なグラフサポートがまれな理由は複数の要因が重なっているためである
    • グラフ種類が多い
    • 各グラフ種類ごとに表現方式が多い
    • グラフアルゴリズムの種類が多い
    • アルゴリズム性能が表現と実装の細部に敏感である
    • 人々は非常に大きなグラフ上で非常に高コストなアルゴリズムを実行する
  • 言語の標準ライブラリは、あまりに多くの設計判断とトレードオフ、保守負担を引き受けなければならない
  • プログラマがサードパーティのグラフライブラリを避ける理由もある
    • ライブラリが制約的すぎることがある
    • 汎用ライブラリが性能要件を満たせないことがある
  • グラフはシステム分析には有用だが、実装段階ではデータ表現とアルゴリズム選択を自分で直接制御しなければならないことが多い

付録: グラフ型を提供する言語と関連ツール

  • グラフ問い合わせ言語（GQL）は、グラフデータベースにおけるSQLに相当する役割を持つ
    • 広く使われる標準はないが、代表例として SPARQL とNeo4jの Cypher がある
    • ここでいうGQLは、開発中の GQL 標準言語と混同してはならない
  • GraphQL はグラフ問い合わせ言語ではなく、その名前は Facebook Graph Search とのつながりに由来する
  • GQLとSQLの主な違いは、関係、すなわち “join” が第一級エンティティである点にある
    • 映画と人物のデータセットでは、SQLは「出演」「監督」「制作」の関係をそれぞれ many-to-many テーブルで実装する
    • SPARQLでは関係がエッジなので、「映画Yで何らかの役割を担った人とその役割」を簡単に問い合わせられる
  • GQLはエッジ反転、合成、推移閉包のようなエッジ操作もサポートできる
    • SPARQLは経路長や経路上の計算、例えば2人の俳優をつなぐ映画チェーンの収集は提供できない
    • これを支援するGQLははるかに複雑になる
  • 形式仕様言語 Alloy は relation データ型に便利なグラフ走査 primitive を備えており、グラフ表現を扱うのは一般的なプログラミング言語より容易である
    • ただしこれらの primitive はラベル付きエッジに基づいており、他のグラフ表現には合わないことがある
  • Pythonは2020年に graphlib を追加した
    • TopologicalSorter 以外のメソッドはない
    • グラフはノード dict だけで受け取る
    • a -> b グラフを {b: [a]} のような逆向き dict で表現する
  • 2023年時点でCPython内部では graphlib は使われていない
    • GitHubで graphlib を参照するファイルは900個未満である
    • 同じ年に追加された zoneinfo は6,000個超のファイルで現れる
    • def topological_sort( という表現は4,000個のファイルで現れる
    • 自前実装の topological sort は graphlib とは別のグラフ表現を使っていることが多く、変換しにくい
  • 標準ライブラリにグラフ型がある他の例として Erlang と SWI-Prolog がある
  • 「すべてがグラフ」であるプログラミング言語もある
    • 例として GP2 と Grape がある
    • 現状では非常に学術的な領域である
  • Mathematica、MATLAB、Mapleのような数理ソフトウェア言語も、何らかの形でグラフライブラリを備えている
  • 2024年3月18日の更新で、この記事への一部コメントは別ページ にまとめられた

関連記事

1件のコメント

 
GN⁺ 2024-03-05
Hacker News のコメント

  • Graphviz には、ほかのプロジェクトでは使われていない独自の基礎グラフライブラリがあり、長所も短所もある
    その経験を踏まえると、私たちも典型的なセカンドシステム症候群に陥っていた。モジュール式で、型安全で、効率的なグラフライブラリを作りたかったのだが、結局は「良い・速い・安い――選べるのは2つだけ」の変種だった可能性が高い
    モジュール式というのは、グラフアルゴリズムのライブラリ群を独立に開発・コンパイルできるようにしたい、という意味だった。型安全というのは、「ノードに color 属性がない」といった実行時エラーではなく、コンパイル時、遅くともリンク時にはプログラミング上の誤りを捕まえたい、という意味だった
    効率的というのは、グラフ属性へのアクセスコストが C の構造体フィールドアクセス並みに安くあるべき、ということだった。外部のハッシュテーブルを持ち歩いたり、文字列変換を多用したりする方式は望んでいなかった
    これらの目標が対価に見合うものだったのか、筋が通っていたのかは議論の余地があるが、当時の私たちが欲しかったのはそういうものだった。研究所には有名な C++ の創始者たちがいて、C++ にもう一度チャンスを与える気もあった
    インターンからそのまま一緒に働くことになった Gordon Woodhull は優れたプログラマーで、テンプレート C++ でこの種のグラフライブラリ実装を書いた。ソースも https://www.dynagraph.org/ に公開されている
    ほかのメンバーは、そのコードがどう動くのか最終的に理解できるのか確信が持てなかったため、有名な C++ の発明者たちとコードレビューを行った。大量のコード画面と沈黙の末に、「たぶん動く」という結論になった。その時点で、すでに複雑さの崖を越えていたかもしれないと分かった
    コンパイル時のテンプレートエラーは、1つのエラーだけで画面全体を埋め尽くし、C++ の発明者だけが愛せそうな詳細を吐き出した。悪いのは私たちだったし、Gordon はそのまま突き進み、動的グラフレイアウトを Microsoft OLE 上でも動くようにした
    振り返れば、あれは私たち自身の Project Xanadu だったのだろう。私たちがそこで道に迷っている間に、Gephi（Java）、NetworkX、NetworKit（Python）のようなものが登場した。Graphviz の一部を書いた優秀なソフトウェアエンジニア John Ellson は、本流の作業を再び立て直した

    • Graphviz の dot 構文を NetworkX でパースして、高価なツールの実行計画を立てられるし、グラフ構造のおかげで自動並列化もできる

  • グラフを扱う作業をかなりしてきた立場から、「なぜプログラミング言語には組み込みのグラフデータ型がないのか？」という質問を数え切れないほど受けてきた
    今では「ちゃんと作るのが本当に難しい」と信じてほしい、と言うだけでなく、この記事のようなより深い分析を示せるのでうれしい

    • その質問で少しおかしいのは、たいていの言語には木構造すらないという事実を見落としている点だ
      ほとんどの言語が構造的な型として提供しているのは、静的配列、動的配列、連結リストくらいである。二分探索木やハッシュテーブルのようなものは、基盤となる構造の一部の能力を隠す意味的抽象化であって、純粋な構造表現ではない
    • グラフは要件によって表現方法が大きく変わる幅広いデータ構造なので、ドメインレベルで実装するほうが合理的だと考えていた
      記事の「実装の選択肢が多すぎる」という部分も同じ話をしている。その後 Petgraph [0] を見て、初めて汎用グラフライブラリをまともに調べ、かなり興味深いと思ったが、それでもグラフはドメインレベルで実装し続けてきた
      [0] https://github.com/petgraph/petgraph
    • 逆の経験もあった。Tcl で初めてグラフ処理をしていたとき、標準ライブラリにグラフアルゴリズムなどないだろうと当然のように思っていたが、実は存在していて、そのおかげで車輪の再発明をせずに済んだ
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • 「ちゃんと作るのが本当に難しい」よりも重要なのは、トレードオフが多いという点だ
      ほぼすべての言語はハッシュマップを提供しており、特定の状況では自前で実装すればもっと速くできるとしても、標準実装はおおむねうまく機能する。グラフで同じことをするのは難しく、もし可能だとしても複数のグラフ型を提供する必要があるかもしれない
      ついでに言うと、Java の HashMap は、ほかの多くの言語と違って負荷率を調整できる点が少し珍しい
    • とても素朴な考えかもしれないが、ポインタは事実上のネイティブなグラフ型だと思っている
      人々が欲しがっているのはグラフ型そのものではなく、グラフを走査するためのツールに近い

  • グラフはデータ構造やデータ型というより、抽象化だと思う
    根本的にグラフを定義するのに必要なのは、頂点集合 v \in V と関数 Neighbors(v) だけであり、基礎的なグラフアルゴリズムの大半には本当にそれで十分だ
    それ以外はケースごとの制約である。A->B が B->A を意味するのか、ノード集合が特定の制約下で分割可能なのか、色やラベルがあるのか、といったことだ
    さらに一般化すればハイパーグラフにまで進める。この場合は、頂点集合と、頂点集合たちの集合があればよい。関心事に応じて無数の方法で表現でき、通常のグラフはその特殊な場合にすぎない
    データベースの観点では、クエリ最適化とインデックス付けの問題として見ることもできる。グラフにどんな質問を投げたいかによって、よりうまく答えられる表現方法は変わる。「テーブル」という抽象化を表現する方法が1つではないのと同じく、「グラフ」も1つの方法で済むものではない

    • グラフがどこにでもあるのは、それだけ抽象的だからだ
      純粋な数値と同じ抽象レベルにある。有用な「数値」ライブラリがあるように、有用な「グラフ的」ライブラリもあるとは言えるが、「数」ライブラリや「グラフ」ライブラリというものはあまりない。そうした概念は API を作るには抽象的すぎる
    • 頂点集合と Neighbors(v) だけでも、すでに制約が大きい。同じ隣接先へ向かう多重辺を許さないからだ
    • ハイパーグラフが頂点集合と頂点集合たちの集合だとすると、ファイルシステムにも少し似て聞こえる
      ファイルが頂点で、ディレクトリが入れ子にできる頂点集合、というわけだ

  • 主な障害は2つある
    単純で小さなグラフ問題なら、ベクターのベクターで作る隣接リストを自分で組んでも十分簡単で、複雑で巨大なグラフ問題では、解こうとしている問題の詳細に合わせてグラフ実装をカスタムメイドしなければ性能が出ない
    そのため、どんな言語サポートが役に立つのかがよく見えない。コードを分析して、隣接リスト、行列、3次元配列など何が最適かを判断する超賢いコンパイラでもない限り難しい。そうした最適化は、しばらくはコンパイラでは見られないだろう
    Stroustrupが見た現象のもう一つの例だ。私たちはベクターのような小さなものや、OSのような大きなもののコード共有はうまくやるが、中規模の問題はうまく共有できない

    • 小さなものも本当にうまく共有できているとは言い難い。プログラミング言語ごとにベクター実装が別々にあるからだ
      1つの言語エコシステム内ではベクターAPIが小さく、そのため共有しやすいように見える。OSは内部の複雑さに比べてAPIが相対的に小さく、数値計算ライブラリも同様なので共有がうまくいく
      一方、複雑なデータ構造のように、より多くカスタマイズしようとするほどAPIは複雑になり、共有は難しくなる。結局、共有可能性は共有対象の表面積、つまりAPIの相対的な大きさに左右されるようだ
    • 抽象グラフ型を対象に書かれたアルゴリズムを見て、特定のアルゴリズムに合わせて実装を埋め込み最適化する作業は、コード特化型LLMの領域にかなり合っているように見える

  • Electric ClojureはClojure自体のS式をグラフ記述構文として使い、マクロでリアクティブなクライアント/サーバーシステムのデータフローを具体化する
    ここではフルスタックのユーザーインターフェースがユースケースだが、アイデアは一般化できる。https://github.com/hyperfiddle/electric の創業者である
    「グラフ型はみんなどこへ行ったのか？」への答えは、グラフ記述DSLはスコープ、制御フロー、抽象化を表現する必要があり、そうなると実質的に評価モデルから解放されたプログラミング言語と同型になる、ということだと考えている。PythonやTypeScriptでは、完全なプログラミング言語を埋め込むのはかなり難しい
    ブログ記事 “Four problems preventing visual flowchart programming from expressing web applications” も参考になる
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • この記事は主に「なぜプログラミング言語はグラフアルゴリズムをもっとよくサポートしないのか」に答えており、一般的なグラフサポートというよりは、「ビッグデータ」のグラフ処理により焦点を当てているように思える
    グラフサポート全般で見ると、「なぜOGM（Object Graph Mapper）はORMほど人気がないのか」「なぜJSONは広く使われているのに、RDFや他の低レベルのグラフシリアライズはそうではないのか」といった、より広い問いも含まれる
    結局、歴史的な理由が大きいと思う。RDFは少し早すぎる時期に登場し、適切に進化できず、ひどい学術標準と実装エコシステムを築いてしまった。さらにグラフは、実装と学習曲線の面で本質的に少し複雑なので、多くの開発者にはうまくスケールしない
    記事の「Graph Querying Language」の部分には、あまり大きな重みは置かない。Neo4JやSPARQLの熱心なユーザーが、実際にプロダクトを作ってみずに書いたマーケティング文句のように読める箇所がある
    「すべてのGQLとSQLの主な違いはJOIN、つまり関係が第一級エンティティである点だ」としているが、SQLでもJOINは第一級エンティティだ。JOINというキーワードさえある
    グラフクエリ言語のより低い層に降りてクエリ計画を見ると、SQLベースのクエリと意味のある違いはあまりない。GQL[0]の標準化がSQL拡張として進められていることがその証拠だ
    SPARQLは正確な経路トラバーサルが必要なときは簡単だが、Webアプリのバックエンドでやりそうな、もう少し複雑なことをしようとすると、バインドされていない値とのJOINのように、結果セット全体をうっかり吹き飛ばしてしまう罠にすぐぶつかる
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • 独自のキーワードがあるというのは、むしろ何かが第一級オブジェクトではないという強い証拠に近い
      例えばHaskellの型クラスは第一級ではなく、ほとんどのプログラミング言語で制御フローも第一級ではない
    • JOIN、とくにRECURSIVEクエリにおけるJOINはグラフデータベースの中核なので、SQLリレーショナルデータベースも概してうまく処理する
      ただし構文上の近道がないだけで、グラフクエリ言語は本質的にその近道を追加することに焦点を当てている

  • グラフ描画ツールもかなり期待外れ。小さなグラフではうまく動くが、ノードが500個を超えるあたりから、出力がまったく理解不能になるか、非常に見づらくなる
    グラフを階層構造として自動整理し、探索しやすいインターフェースを提供する能力が不足している。私たちが身の回りのあらゆるものをある程度 階層構造 として見ることに慣れている点を考えると、汎用グラフ型を作る際にも同じ種類の問題を解く必要がありそうだ
    こうしたことはコンパイラレベルで実装され、汎用グラフアルゴリズムが生成された構造階層に適応する必要があるのかもしれない。ここに定理証明器を加えて、特定の部分グラフが常に特定の構造を持つことを確認できれば、その手続きは静的に生成し、残りの上位グラフについては実行時に動的生成できる
    したがって 汎用グラフ描画 の問題を解く人は、この問題を実装する能力や洞察も持つことになるだろう

    • グラフ描画は難しい
      Graphviz系の汎用グラフ描画ライブラリで、より多くのオプションと制御を提供する
      https://eclipse.dev/elk/
      Kiel UniversityのELK開発チームが行った実験
      https://github.com/kieler/KLighD
      KielerプロジェクトのWiki
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      制約ベースのグラフ描画ライブラリ
      https://www.adaptagrams.org/
      JavaScript実装
      https://ialab.it.monash.edu/webcola/
      興味深い資料として HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Confluent Graphsのデモはエッジをより読みやすくしてくれる
      https://www.aviz.fr/~bbach/confluentgraphs/
      Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
      https://arxiv.org/pdf/1408.4626.pdf
      Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
      https://arxiv.org/pdf/1311.6996v1.pdf
    • ある種のアルゴリズムはこの問題をよりうまく扱えるが、一般的には「グラフの良いダイアグラムを作れ」というのは AI完全問題 に近い
      構造的には同じグラフでも、2人の人間がデータの異なる側面を強調しようとして、まったく違う形でレンダリングすることがある。これは「汎用グラフアルゴリズム」や「汎用グラフデータ構造」の問題にも似ている
      グラフはコードとデータの境界にまたがっている。例えばどんなプログラムにも呼び出しグラフがあるので、ある意味では「汎用グラフアルゴリズム」は計算そのものだ
    • 理想的なものはたいてい木のように見えるが、現実世界の構造は、きちんと整理されていても通常は 有向非巡回グラフ である
      ノードが数十個を超えるだけで、平面的にしたり、交差を少なくして関連ノードをうまくまとめ、ほぼ平面に見えるようにしたりするのはたいてい難しい
    • 私たちが、すべては階層的だと信じる 幻想 に慣れていることのほうが大きな問題だと思う
      実際にはほとんど階層的でないものをグラフ描画が折り合わせなければならず、どこまでを階層と見るかを数学的に厳密に線引きするのは難しい。基礎となるグラフ構造について、連結性、巡回の有無、疎性といった仮定を少なくするほど、この問題は悪化する
      実務でグラフと相互作用するUIを作るときは、たいてい1〜2段階のメタ階層を決める、または強制してクラスタリングできる。そうすれば、hairballノードがレイアウトを壊す影響を減らし、ノード数も減らしてレンダリング性能も改善できる。レイアウトにはfCOSEを使え、Cytoscape.js実装もある
    • ニューラルネットワークの図を見ると、大規模グラフ可視化 がどれほど完全に理解しにくくなるかがよく分かる

  • 核心的な観察である「実装の選択肢が多すぎる」という点は、完全には正しくないと思う
    実際には、ライブラリは適切なグラフ表現をすべて実装し、それぞれの表現で最も性能のよいアルゴリズムを提供し、表現間の変換も提供できる。この変換は表現の数に比例し、実装も利用も単純なので、メンテナーとユーザーの双方にとってかなり妥当な負担だと思う
    おまけに、標準ライブラリのデータ型やイディオムとのインポート/エクスポート変換も提供できる。メモリと変換コストは安く、ユースケースの99%では、RAMとCPUの両面でデータ変換のオーバーヘッドを無視できる可能性が高い
    「Googleで働くことの厳しい真実は、結局protobufをある場所から別の場所へ移しているだけだ」という言葉も思い出す
    https://news.ycombinator.com/item?id=20132880

    • そうすると巨大なライブラリになりそうで、自分の仕事で使うかは確信がない。私はグラフを多用しているが、経験は筆者がインタビューした人たちと似ている
      結局いつもグラフを再実装することになる。性能が重要で、私が見た既製のグラフライブラリは、私たちのデータセットの規則性を活用できなかった。たとえば私たちはappend-only DAGを使っているが、ほぼすべてのノードが最後に追加された項目を指す辺を1本だけ持っているので、内部的にはランレングス符号化が可能だ
      必要なクエリをサポートする汎用グラフライブラリも見たことがない。特に大きいのは部分グラフdiff関数だ
      そのうえ、カスタム実装はそれほど手間ではない。グラフはB-treeよりはるかに再実装しやすく、単純な実装なら数十行で済む。対応アルゴリズムまで含めた高度に最適化された私たちのライブラリでも数百行程度だ
      データを標準形式でエクスポートする方法があれば便利だが、私たちのユースケースでは、ライブラリを引き込むほうが解決より問題を増やしそうだ

  • よく思い浮かべていた欠けているアプリケーションはグラフ用Excelだ
    表形式データ向けのExcelのように、RAMに収まる程度のデータ、つまりコンピュータは必要だがデータセンターまでは不要な規模を扱い、多くのアルゴリズムと可視化を「十分に良い」形で実装し、プログラミング知識がなくても使えるツールだ
    記事が述べているように、現実の多くの問題はグラフ問題なのに、なぜプログラマーだけがその問題を解く道具を持つべきなのか

    • 記事は結論を急ぎすぎている気がする。他の多くの問題も、要件を追加すればいくらでも複雑で難しくできる
      それでも、ほとんどのユースケースに十分合うデータ構造と標準ライブラリは存在し、特別に厳しい要求があればカスタムソリューションを作ればよい
      記事はグラフが大きすぎることが多いと言っているが、グラフアルゴリズムを実際に扱う人に聞けば、そういう経験をしやすい。ほとんどのプログラマーとユーザーは、おそらく本当に小さなグラフしか扱わないだろう
    • プログラマーと数学者だけが、こうした問題をグラフとしてモデル化しているのだと思う
      一般ユーザーがランダムな現実の問題にグラフを見いだすとは思わない。大企業で働いて学んだのは、十分に努力すればあらゆるものはExcelスプレッドシートになり得るということだ
    • 正確に求めていたものではないが、https://gephi.org/ は多くのグラフ可視化アルゴリズムを実装している
      https://strlen.com/treesheets/ はツリーデータ用Excelに近い
    • 記事は「現実の多くの問題がグラフ問題である」という点を十分に裏付けていない
      たとえばインターネットをグラフとしてモデル化できると言っているが、それが正しいとして、それで何が得られるのかは不明だ。インターネットはさまざまな方法で表現でき、グラフで表現することが一般に有用な工学的含意を持つという点は明らかではない
      有用な情報を得るための理想的な表現は、むしろ任意の入力を一貫した出力へ写像するブラックボックスの行列エンコーディング関数、つまりニューラルネットワークだと言っても、同じくらい説得力がある
      Googleのようなところには数十億ドル規模のアイデアかもしれないが、インターネット全体が多くの人にとってグラフ問題であるわけではなく、グラフで表現したからといって多くが解決するわけではない
      現実の問題を紙の上でグラフとして解いている人はまれだ。表は常に使われる。グラフは一般的だが、グラフ問題は一般的ではない
    • ここでの鍵はVRだと思う
      他のコメントでもグラフ可視化は難しいと言われていたが、3Dインターフェースははるかに多くの空間を与えてくれる。VRブームが始まったとき、「VRのExcelは何だろう？」と考えたが、Microsoftの答えは「3D空間に浮かぶ2Dスプレッドシート」だった。あり得ないと思う。私はグラフだと思う
      一緒に探求したい人がいれば、私のユーザー名 at gmail.com までメールしてもよい

  • グラフ型はかなり昔からあった
    Erlangには https://www.erlang.org/doc/man/digraph.html と https://www.erlang.org/doc/man/digraph_utils があり、集合論的な処理をしたいなら https://www.erlang.org/doc/man/sofs.html もある

    • 記事の終盤でErlangが短く取り上げられている
      「グラフ型がある他の2つの言語としてErlangとSWI-Prologを見つけた。どちらもよく知らないので、いつ追加されたのかは言えないが、Erlangには少なくとも2008年以前には存在していた。Erlangコア言語委員会の人に連絡したが、返事は得られなかった」という内容だ
    • Elixirにもかなり良いグラフライブラリがある: https://hexdocs.pm/libgraph/api-reference.html
      作業順序を決めるための依存関係解決に使ったことがある
    • それがさまざまな状況でどれほど柔軟で、性能がよく出るのか気になる