The Graph Mining Library - グラフアルゴリズムおよび分析ライブラリ

 (github.com/google)
3 ポイント 投稿者 GN⁺ 2023-10-05 | 1件のコメント | WhatsAppで共有
  • Google Graph Mining チームの目標は、グラフアルゴリズムと分析のための高い拡張性を持つライブラリを構築し、Google 製品に適用すること。現在の提供範囲は クラスタリングアルゴリズム のコレクション
  • 開発対象のツールは、類似度グラフの構築、クラスタリング、ノード分類、ノード埋め込み、グラフニューラルネットワーク学習、グラフ可視化、各種サンプリング、類似度ランキング
  • クラスタリング分野は、数百億本のエッジを持つグラフまで拡張可能な 共有メモリ並列アルゴリズム と、複数の逐次アルゴリズムで構成
  • 並列アルゴリズムは、HAC、相関クラスタリング、affinity clustering、parline に関する研究論文に基づく実装
  • Graph Neural Network フレームワークは、別プロジェクトの TF-GNN で提供
  • すぐに試すには、Bazel をインストールした後、bazel run //examples:quickstart を実行
  • Google の公式サポート製品ではなく、質問や意見はこのリポジトリで issue を作成して受け付ける

関連記事

1件のコメント

 
GN⁺ 2023-10-05
Hacker News のコメント

  • グラフマイニングは10年ほど前に本当に流行していました。GraphX (https://spark.apache.org/graphx/) や GraphLab (https://en.wikipedia.org/wiki/GraphLab)、グラフデータベースを思い出します。
    おそらくソーシャルネットワーク現象と時期が重なっていたのだと思いますし、より最近では、グラフやその他の構造上の機械学習である幾何学的学習が注目されていましたが、LLMに話題を奪われました。それでも幾何学的学習にはまだ大きな可能性があると思っており、もっと人気が出てほしいです。

    • 「グラフデータベース」には、グラフをデータへの普遍的なアプローチと見る流れがあり、RDFやSPARQL、数多くの類似した試みがあります。Cプログラムでは、中心的なデータ構造がポインタグラフである場合も考えられます。
      こうしたグラフには通常、「〜と結婚している」「年平均気温を持つ」といった、互いに異なるエッジ種別が非常に多くあります。一方で、PageRankやグラフ中心性のようなグラフアルゴリズムは、エッジ種別が1つ、またはごく少数であることが多いです。複数種類のエッジを持つグラフにも適用できる一般的なアルゴリズムはあります。たとえばSPARQLパターン ?s1 ?p ?o . ?s2 ?p ?o . は、ある ?o と関係 ?p を共有する ?s1、?s2 を見つけ、両者の類似度指標の基礎になります。グラフは一般に形が決まっておらず、どんな構造にもなり得るため、メモリレイテンシの観点では災厄になり得ます。以前このSPARQLパターンを使っていて、100年かかるプログラムを作ってしまったことがありますが、データ構造を再パックし、近似を見つけることで20分以内に計算できるようにしたことがあります。そのため実務者は、汎用グラフ処理ライブラリに懐疑的な傾向があります。ビルドシステムと格闘する時間より短い時間で専用コードを書き、1000倍高速にできる問題がよくあるからです。
      それでも流行を追いたいなら、最近のarXivには、他の場所ではそこまで大げさに扱われていないグラフニューラルネットワークの論文があふれています。YOShInOnが読むべきGNN論文の長いリストを作ってくれましたが、いくつかざっと見ただけです。私が扱っているテキスト分析問題に適用できるという論文は多いものの、YOShInOnと私が使っているシステムより特に良さそうには見えないので、急いではいません。
    • グラフ分析で解くのが最適な問題では、今でもNetworkXをよく使っていますし、このパッケージの開発者体験は本当に気に入っています。

  • グラフと機械学習を触ってみたい人なら、最近ArangoDBのドキュメントを見ていたところ、複数のグラフライブラリや機械学習フレームワークとの統合が含まれているのを見かけました https://docs.arangodb.com/3.11/data-science/adapters/
    グラフで機械学習を扱うJupyterノートブックもいくつかありました https://github.com/arangodb/interactive_tutorials#machine-learning
    統合対象には、NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/ があります。

  • Bazel に詳しい人がいれば、ビルド方法のヒントをもらえないだろうか？ bazel build は何かはしているようだが、結果として bazel-build と bazel-build だけができて、目立ったビルド成果物が見当たらない

    • Bazel で //... は make の all ターゲットに近い
      bazel build //...、bazel test //...、bazel query //... のように使えばよい。最後のコマンドは、記憶ではすべてのターゲットを列挙してくれるはず
    • 上の回答に付け加えると、単一パッケージだけをビルドすることもできる。たとえば bazel build //in_memory/connected_components:asynchronous_union_find で asynchronous_union_find をビルドできる
      ただし cc_binary ルールの文脈の外では、それほど有用ではないかもしれない。この方法ならリポジトリ全体をビルドせずに、別プロジェクトで必要なパッケージだけをビルドして使える。たとえば asynchronous_union_find.h ヘッダーだけを使いたいなら、プロジェクトの WORKSPACE ファイルのどこかに git_repository ルールで graph-mining ライブラリを追加し（WORKSPACE.bazel の例を参照）、プロジェクト内の BUILD ファイルにある cc_library ルールへ @graph-mining//in_memory/connected_components:asynchronous_union_find を追加すればよい。そうすれば他の場所からヘッダーとしてインクルードでき、プロジェクトのビルド時にはそのパッケージと依存関係だけがビルドされ、graph-mining ライブラリ全体はビルドされない
    • 前からいつか Bazel を確認してみないと、と思っていただけだったが、その「いつか」が今日になった。インストールするにはまず Bazelisk を入れてから名前を bazel に変え、/usr/local/bin/bazel のようなパスに置くのが推奨される方法らしい
      ところが query を実行すると JDK の警告が出て、build を実行すると WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE. と出たうえで Java がなくて失敗した。Java を使っているわけでもないのに、どの JDK/JRE を使えばいいのか数分検索して、もう無理になったので、今日の「いつか」はまた別の日になった。cargo や npm/yarn に慣れすぎているのが情けないほどだ
      追記: https://sdkman.io/ のおかげで動いた。結局そこまで悪くはなかった

  • 初歩的な質問だけど、このライブラリはラッパーや拡張ライブラリと統合して、グラフベースのクラスタリングアルゴリズムを一か所に集める候補と見なせるのだろうか？ まだそうなっていないという前提で
    それとも、同じ機能をもっとよく提供するフレームワークがすでにあるのだろうか？ NetworkX のようなものだ

  • 自分が時代にかなり取り残されているだけかもしれないが、これは Pregel と関係があるのか？

    • Pregel は分散グラフ処理システムで、これは私には単一コンピュータのメモリ内でグラフを扱うライブラリに見える

  • 例があると本当に助かる

    • どんな形でもドキュメントがあると本当に助かる
    • 近いうちに公開される予定。12時間後にもう一度確認すれば、おそらくあると思う

  • このライブラリがどこで役に立つのか説明してもらえるだろうか？

    • クラスタリングに使える。類似度の尺度（このデータはあのデータに似ている）と強い反発の特徴（このデータはあのデータとは異なると分かっているので、絶対にマージしない）を持つノードグラフとして表現できる問題に、ここにある相関クラスタリング器を使ったことがある

  • GitHub では C、C++、Starland と書かれている。Starland って何だ？

    • Starlark だ。Bazel ビルドシステムを設定する言語で、Bazel は Google 内部のビルドシステム Blaze のオープンソース移植版。Starlark は Python のサブセットだ
    • 推測だがタイプミスで、Starlark のはず。Bazel のビルドファイルで使う言語だ
      Bazel はここで使われているビルドシステム

  • グラフアルゴリズムにはある程度の標準化が切実に必要だ。BLAS と LAPACK を考えればいい

  • 文字どおり統計グラフをマイニングして異常検知するツールであることを期待していた