著者：シェン・ウェンティン

GraphLearnは、Alibaba Cloud Machine Learning Platform（PAI）チームとDAMO Academy Intelligent Computing LabのGraph Computingチームが共同開発した産業規模のグラフニューラルネットワークトレーニングフレームワークです。また、ワンストップグラフコンピューティングプラットフォームGraphScopeのグラフ学習エンジンでもあります。GraphLearnは最近、動的グラフGNN推論のためのオンラインリアルタイムグラフサンプリングサービス（DGS）をオープンソース化しました。DGSは、リアルタイムの高スループットグラフ更新を処理でき、低レイテンシで高並行性の推論サンプリングクエリ処理を保証します。そのグラフ更新とサンプリングクエリのパフォーマンスは、分散環境において線形にスケーラブルです。最近、GraphLearnチームと浙江大学は共同で「 Dynamic Graph Sampling Service for Real-time GNN Inference at Scale 」を発表し、EuroSys 2023の最優秀ポスターに選ばれました。

背景紹介

GNNモデルは、高次の近傍情報をグラフ構造を通して表現します。大規模な産業展開では、近傍サンプリングによって通信と計算のオーバーヘッドを削減し、分散スケーラビリティを実現することが一般的な学習手法です。一方、レコメンデーションシステムや金融詐欺防止といった現実世界のビジネスシナリオでは、グラフの構造と特性が時間の経過とともに動的に変化することがよくあります。GNNモデルは、こうした動的な近傍情報をリアルタイムでサンプリングし、表現できる必要があります。

オンライン学習はモデルのジッターを引き起こしやすく、実際の本番環境ではモデルのデプロイメントに複雑なプロダクションチェーンが必要となるため、デプロイメントにはニアラインモデルが一般的に用いられます。GNNモデルが近傍情報をリアルタイムに表現するためには、 GNNモデルの推論プロセス中にグラフ構造と属性をリアルタイムにサンプリングし、リアルタイム推論を実現する必要があります。

優れたユーザーエクスペリエンスを確保するため、このリアルタイム推論タスクでは極めて低いレイテンシが求められ、サンプリングクエリのためのレイテンシマージンはほとんど残っていません。さらに、産業用グラフの規模とオンライン推論サービスのQPSは、単一のマシンのストレージ能力と計算能力を超えることがよくあります。そのため、大規模な動的グラフにおいて極めて低いレイテンシ（P99で20ミリ秒以内）を保証し、分散環境で線形にスケーリングできる能力を備えた、GNNモデル推論用のリアルタイムサンプリングサービスを提供する必要があります。

チャレンジ

リアルタイムグラフサンプリングサービスへの直感的なアプローチは、動的なグラフストレージとクエリモジュールを維持することです。推論リクエストが到着すると、要求されたポイントに対して近傍サンプリング計算と属性収集が実行され、これらの計算から得られたサンプルが推論中のモデルサービスの入力として使用されます。しかし、グラフデータの分散性と推論サンプリングの負荷特性により、分散型動的グラフ上で安定した低レイテンシのサンプリングを実現することは困難です。具体的には、以下の課題が存在します。

1. 近傍サンプリングではすべての近傍を走査する必要があり、グラフが動的に変化すると近傍も常に変化するため、複雑なサンプリング計算において低レイテンシを保証することが困難になります。外れ値の存在もレイテンシの不安定性を引き起こします。
2. グラフ データが不均一に分散されているため、各グラフ シャードのストレージと計算負荷が不均一に分散され、サンプリングの待ち時間が不安定になり、分散方式での線形スケーリングが困難になります。
3. 推論サンプリングは通常、マルチホップサンプリングであり、頂点またはエッジ上の動的な属性の収集を必要とします。分散グラフでは、マルチホップサンプリングと属性アクセスによって発生するネットワークおよびローカルI/Oのオーバーヘッドがレイテンシに大きな影響を与えます。

キーデザイン

一般的なグラフデータベースのワークロードとは異なり、動的グラフ推論サンプリングサービスは、特定のモデルに対するオンライン推論を提供する際に、グラフサンプリングに固定パターンを採用します。例えば、一般的なユーザー-アイテム、アイテム-アイテムの二部グラフGraphSAGEモデルでは、通常、リクエスト元のユーザーID（feed_id）から、タイムスタンプに基づいて最近購入された2つのアイテムをサンプリングし、次にこれらの2つのアイテム間で相関係数が最も高い2つのアイテムをサンプリングします。これは、GraphLearnのGSL（グラフサンプリング言語）を使用したクエリとして表現できます。

図1: 2ホップサンプリングクエリ

固定パターンを持つこのタイプのクエリは、大規模な動的グラフ サンプリングに対して安定した低レイテンシのサービスを提供する機会を提供します。

DGS システム設計の主な側面:

1. ストレージとコンピューティングの分離とクエリキャッシュ

DGSはグラフの保存とサンプリング計算を分離します。サンプリング計算とは、一般的にランダムサンプリング、トップkタイムスタンプサンプリング、またはエッジウェイト（またはエッジタイムスタンプ）を使用した確率分布サンプリングを指します。最初の2つのサンプリング方法の時間計算量はO(1)ですが、確率分布サンプリングは通常、エイリアス法を使用して実装されます。エイリアステーブルは、動的グラフ内の変化する確率分布について繰り返し計算する必要があり、その結果、O(N)の時間と空間の計算量が発生します。ここで、Nは連続的に変化する頂点の近傍数です。グラフ保存の単純な読み取りおよび書き込み操作とは異なり、グラフサンプリングプロセスには、ストレージの読み取りおよび書き込み操作と複雑な計算の両方が含まれます。そのため、まず保存と計算を分離します。計算側では、システムはサービスの特定のクエリに必要なデータを事前にキャッシュして、グラフサンプリング計算の空間的局所性を向上させます。

1. イベント駆動型プリサンプリング

サンプリング要求への応答を高速化するために、DGS は、要求入力の瞬間からグラフ更新イベントの発生の瞬間まで各頂点のサンプリング計算を進め、スペースと時間をトレードオフすることで、サンプリング要求が発生したときに頂点のルックアップのみが完了すれば済むようにします。同時に、グラフ更新イベントの発生とサンプル生成の間の古さを減らすために、DGS はストリーミング サンプリングを採用しています。重み付けリザーバ サンプリング アルゴリズムを使用して、ストリーミング サンプリングは、更新が到着するたびに事前にインストールされたクエリに基づいて実行されます。このグラフ更新イベント駆動型の事前サンプリング アプローチにより、各頂点のグラフ データのストレージ スペースと計算時間は定数 * O(K) になります (K はリザーバのサイズ)。グラフ サンプリングの計算結果をキャッシュに事前保存することで、課題 1 の問題が解決されます。

1. マルチホップ逆アセンブリと遅延アセンブリ

このように、DGS は入力頂点のリアルタイム 1 ホップ サンプリングの問題を解決しました。ただし、DGS は主にマルチホップ サンプリングを提供します。2 ホップ サンプリングを例にとると、入力頂点の 1 ホップ結果が更新された後、対応する 2 ホップ結果も更新する必要があります (収集された属性も同時に更新されます)。ホップ数が多いと、この連鎖反応により読み取りと書き込みのオーバーヘッドが指数関数的に増加し、サンプリング要求のレイテンシに大きな影響を与えます。DGS は、事前にインストールされたクエリに基づいてグラフ サンプリングをホップに分解することで、この問題を解決します。各ホップ サンプリングでは、グラフ内の対応する頂点タイプのすべての頂点が事前にサンプリングされ、それに応じて保存されます。たとえば、図 1 のクエリは、図 2 に示すように分解できます。イベント駆動型の事前サンプリングと組み合わせることで、図 3 に示すように、各頂点に対応するサンプルがリザーバーに保存され、更新されます。

さらに、DGS は、対応する推論サンプリング要求が発生するまでマルチホップ サンプルの連結を延期し (遅延連結)、早すぎる連結後の継続的な更新を回避します。

図2: 2ホップサンプリングクエリ分解

図3: イベント駆動型アップデート

1. サブスクリプション・パブリッシュメカニズム

マルチホップ連結はリクエストが発生するまで遅延されますが、マルチホップの結果は異なるシャードに保存されることが多く、マシン間通信は大きなネットワークオーバーヘッドを引き起こします。そこでDGSは、パブリッシュ・サブスクライブ方式を設計しました。この方式では、リクエストIDが特定のシャーディングアルゴリズムに基づいて対応するサービスマシンにルーティングされます。このマシンは、これらのIDとマルチホップネイバーの更新をサブスクライブします。ネイバー関係が変化すると、サブスクリプションテーブルは継続的に更新されます。

1. 読み書き分離

上記のシステム設計に基づき、サンプリング要求が発生すると、DGSはそれを指定されたワーカーにルーティングし、そこでローカルクエリによってマルチホップサンプリング結果を取得できます。書き込みの古さを確保しながら読み取りレイテンシを優先するため、DGSは読み取りタスクと書き込みタスクを優先します。さらに、システムアーキテクチャの観点からは、ストレージの計算と更新を頻繁に行うタスク（書き込み）と、サンプリング要求に応答するタスク（読み取り）を別のマシンに配置することで、読み取り操作と書き込み操作を分離しています。

システムアーキテクチャ

DGS システムのコア コンポーネント アーキテクチャを下図に示します。主に、サンプリング ワーカー コンポーネントとサーバー ワーカー コンポーネントで構成されています。

図4: DGSシステムのコアアーキテクチャ

グラフの更新は、キー（例：頂点ID）に基づいて、サンプリングワーカーの対応するパーティションに分散されます。各サンプリングワーカーは特定のパーティションを担当し、ワンホップのプリサンプリングを実行し、その結果をサービングワーカーに送信します。各サービングワーカーは、サンプリングワーカーから受信したK個のワンホップクエリのサンプリング結果をキャッシュし、グラフの特定のパーティション内の頂点に対する推論サンプリング要求に応答します。

サンプリングワーカーとサービングワーカーはそれぞれ独立して柔軟にスケーリングできるため、グラフ更新と推論リクエストの負荷の変化に対応できます。完全なKホップサンプリング結果を生成する際のレイテンシを最小限に抑えるため、DGSは頂点を分割し… すべての K-hop サンプリング結果は事前に応答に送信されます。 推論リクエスト用のサービングワーカーは、Kホップグラフのサンプリング計算を、サービングワーカーのローカルキャッシュへのアクセスのみを必要とする操作に変換します。これを実現するために、各サンプリングワーカーは各ワンホップクエリのサブスクリプションテーブルを維持し、それらのワンホップクエリの結果をサブスクライブしているサービングワーカーのリストを記録します。例えば、頂点…

から ワンホップ サンプルでデータを追加または削除すると、データを含むサンプルにイベントを送信するメッセージがトリガーされます。 パーティションのサンプリング ワーカー。それに応じて更新されます。 サブスクリプション情報。

この設計により、DGS は、同時実行性の高い推論サンプリング負荷下でも非常に安定したレイテンシ パフォーマンスを発揮できます。

パフォーマンス

Alibabaの実際のeコマースデータセットを用いた実験では、DGSは推論リクエスト（2ホップランダムサンプリングクエリ）のP99レイテンシを20ミリ秒以内に抑え、単一のサービングワーカーで約20,000 QPSを達成し、線形にスケールできることが示されました。グラフデータ更新のスループットは109MB/秒に達し、これも線形にスケールします。

図5: 実験セットアップとパフォーマンスデータ

結論

この記事では、DGSの技術的な解説を行い、そのコアモデルの設計原則を紹介します。DGS as a Serviceには、サービス起動モジュール、高可用性モジュール、データ読み込みモジュール、そしてモデルサービスと連携するクライアントも含まれています。DGSを利用することで、ユーザーはリアルタイムに変化するグラフ構造と特徴に基づいて、最新のグラフ表現を推論することができます。GraphLearnとDGSを用いたトレーニング、モデルのデプロイ、オンライン推論のためのエンドツーエンドのチュートリアルも提供しています。ぜひお試しください。詳細については、ソースコードと技術ドキュメントをご覧ください。