動的グラフのディープラーニング - 時系列グラフネットワークモデリング

インターネットから収集したコンテンツ

さまざまな性質のトランザクション ネットワークや社会的つながりを伴う現実世界の問題の多くは動的であり、時間の経過とともにノードとエッジが変化するグラフ構造としてモデル化できます。この記事では、動的グラフ上のディープラーニング モデリングの一般的なフレームワークである Temporal Graph Networks について説明します。

グラフニューラルネットワーク (GNN) の研究は年々劇的に増加しており、今年の機械学習研究で最もホットなトピックの 1 つとなっています。 GNN は最近、生物学、化学、社会科学、物理学などの分野の問題に対して一連の成功を収めています。これまでのところ、GNN モデルは主に、時間の経過とともに変化しない静的ネットワークをモデル化して処理します。ただし、現実世界のグラフ ネットワークの多くは動的であり、時間の経過とともに変化します。典型的な例としては、ソーシャル ネットワーク、金融取引、推奨システムなどがあります。多くの場合、静的なグラフのみを考慮した場合には失われてしまう重要な情報を伝達するのは、このシステムの動的な動作です。

ツイートを通じて互いにつながる、Twitter ユーザーのダイナミックなネットワーク。すべてのエッジにはタイムスタンプが付けられます。このような動的なグラフが与えられた場合、ユーザーがどのツイートを気に入るか、誰をフォローするかなど、将来のエッジを予測したいと考えています。

動的グラフは、ノードやエッジの追加や削除などの時間指定イベントの順序付きリストまたは非同期「ストリーム」として表現できます[1]。 Twitter のようなソーシャル ネットワークは典型的な例です。ユーザーがプラットフォームに参加すると、新しいノードが作成されます。他のユーザーをフォローすると、新しいフォロー エッジが作成されます。設定ファイルを変更すると、ノードが更新されます。

このイベント ストリームは、グラフの各ノードに対して時間依存の埋め込みを生成するエンコーダー ニューラル ネットワークによってエンコードされます。埋め込みの内容は、特定のタスク用に設計されたデコーダーに入力できます。たとえば、「時刻 t にノード i と j の間にエッジが存在する確率はどれくらいか」という質問に答えることで、将来のエッジの役割を予測できます。この質問に答える能力は、ソーシャル ネットワーク ユーザーにどのようなコンテンツを推奨するか、ユーザーがフォローしたいコンテンツを予測するかなど、推奨システムにとって非常に重要です。次の図はこの状況を示しています。

7 つの可視エッジ (t? から t? までのタイムスタンプ) を持つ動的グラフの TGN エンコーダーの例。時刻 t? (灰色のエッジ) におけるノード 2 と 4 間の将来の接続の確率を予測することを目的としています。この目的のために、TGN は時刻 t1 におけるノード 2 と 4 の埋め込み表現を計算します。これらの埋め込みは連結され、デコーダー（MLP など）に送られ、接続されたエッジの存在確率が出力されます。

上記のシナリオの重要なコンポーネントはエンコーダーであり、これは任意のデコーダーと同時にトレーニングできます。前述のエッジ予測タスクでは、自己教師あり方式でトレーニングを行うことができます。つまり、各エポックで、エンコーダーはイベントを時系列順に処理し、以前のイベントに基づいて次のエッジを予測します[2]。

Temporal Graph Network（TGN）は、TwitterでFabrizio Frasca、Davide Eynard、Ben Chamberlain、Federico Montiなどの同僚と開発した汎用エンコーダーアーキテクチャです[3]。このモデルは、イベント ストリームとして表現される動的グラフ上のさまざまな学習問題に適用できます。つまり、TGN エンコーダーは、接続エッジに基づいてノードの圧縮表現を作成し、イベントが発生するたびにその表現を更新します。この目的のために、TGN には次の主要コンポーネントがあります。

メモリユニット。メモリはすべてのノードの状態を保存し、ノードの過去の接続の圧縮された表現として機能します。 RNN の隠し状態に似ています。ただし、各ノード i は独立した状態ベクトル si(t) で表されます。新しいノードが出現すると、ゼロに初期化された新しい状態ベクトルが追加されます。さらに、各ノードのメモリは単なる状態ベクトル (パラメータではない) であるため、モデルが新しい接続を吸収するテスト時に更新することもできます。

メッセージ機能:メモリを更新するための主なメカニズム。時刻 t にノード i と j を接続するエッジが与えられた場合、メッセージ関数は 2 つのメッセージ (1 つは i 用、もう 1 つは j 用) を計算してメモリを更新します。これは、メッセージパッシンググラフニューラルネットワーク[4]で計算されるメッセージに似ています。メッセージは、エッジが接続される前の時刻t?におけるノードiとjのメモリ、エッジ接続の時刻t、およびエッジ特性[5]の関数である。

メモリ更新コンポーネント:新しいメッセージでメモリを更新するために使用されます。このモジュールは通常、RNN として実装されます。

ノードのメモリは時間の経過とともに更新されるベクトルであるため、最も直接的なアプローチは、それをノード埋め込みとして直接使用することです。しかし、実際には、古さの問題 (更新の不一致な同期によって生じる状態ドリフト) があるため、これは適切ではありません。メモリはノードが接続されたエッジに参加しているときにのみ更新されるため、ノードが長期間非アクティブになると、そのメモリは古くなります。例として、数か月間 Twitter を離れたユーザーを考えてみましょう。ユーザーが戻ってきたときには、その間に新たな興味が芽生えている可能性があるため、過去のアクティビティの記憶はもはや重要ではありません。したがって、埋め込みを計算するためのより良い方法が必要です。

埋め込み。 1 つの解決策は、ノードの隣接部分を確認することです。古さの問題に対処するために、埋め込みモジュールは、ノードの時空間近傍に対してグラフ集約を実行することにより、ノードの時間的埋め込みを計算します。ノードがしばらく非アクティブであったとしても、その近隣ノードの一部はアクティブである可能性があり、それらのメモリを集約することで、TGN はノードの最新の埋め込みを計算できます。私たちの場合、ユーザーが Twitter を使用していなくても、その友人はアクティブなままなので、ユーザーが戻ってきたときには、ユーザー自身の履歴よりも友人の最近のアクティビティの方が関連性が高い可能性があります。

グラフ埋め込みモジュールは、時間的近傍にわたって集計を実行することにより、ターゲット ノードの埋め込みを計算します。さらに、上記のグラフでは、計算ノード 1 の埋め込み時間ノード t?、t?、および t? よりも大きいが t? より小さい時間 t では、時間近傍には時間 t より前に発生したエッジのみが含まれます。したがって、ノード 5 へのエッジは、将来発生するため、計算には参加しません。代わりに、埋め込みモジュールは、エッジ上の特徴だけでなく、近傍ノード 2、3、4 の特徴 (v) とメモリ (s) を集約して、ノード 1 の表現を計算します。この実験はグラフアテンションであり、メモリ、機能、インタラクション時間に基づいてどの隣接要素が最も重要であるかを学習できます。

次の図は、TGN がトレーニング データのバッチに対して実行する全体的な計算プロセスをまとめたものです。

TGN がトレーニング データのバッチに対して実行する計算。一方、埋め込みは、埋め込みモジュールによって、時間グラフとノードのメモリを使用して生成される(1)。埋め込みはバッチ相互作用を予測し、損失を計算するために使用されます（2、3）。一方、これらの同じ接続エッジはメモリの更新にも使用されます (4、5)。

上の図を見ると、メモリ関連のモジュール (メッセージ関数、メッセージ アグリゲータ、メモリ更新コンポーネント) は損失関数に直接影響を与えないようで、勾配更新は行われないため、どのようにトレーニングすればよいのか疑問に思うかもしれません。これらのモジュールが損失関数に影響を与えるためには、バッチ接続エッジを予測する前にメモリを更新する必要があります。ただし、メモリには予測したい内容に関する情報がすでに含まれているため、これによりリークが発生します。この問題を解決するために私たちが提案する戦略は、メモリ バッチを以前のメッセージで更新し、接続エッジを予測することです。次の図は、メモリ関連モジュールのトレーニングに必要な TGN の動作フローを示しています。

メモリ関連モジュールをトレーニングするために必要な TGN 操作フロー。新しいコンポーネントである生のメッセージ ストアが導入されました。これは、過去にモデルによって処理された接続エッジのメッセージ (生のメッセージと呼びます) を計算するために必要な情報を保存します。これにより、モデルは接続エッジによって発生するメモリ更新を後続のデータ バッチに延期できるようになります。まず、前のバッチ データ (1 と 2) に格納された元のメッセージから計算されたメッセージでメモリが更新されます。新しく更新されたメモリ（灰色の接続されたエッジ）は、埋め込みを計算するために使用できます（3）。このようにして、メモリ関連モジュールの計算は損失関数（4、5）に直接影響し、勾配を受け取ることになります。最後に、このバッチ接続エッジの元のメッセージは、将来のバッチデータの使用のために元のメッセージストア（6）に保存されます。

様々な動的グラフでの広範な実験検証の結果、TGNはリンク予測と動的ノード分類のタスクにおいて、精度と速度の点で競合方法を大幅に上回っていることが分かりました[6]。そのような動的グラフの 1 つが Wikipedia です。Wikipedia では、ユーザーとページがノードとなり、接続エッジはユーザーがページを編集していることを表します。編集テキストのエンコードは接続エッジ機能として使用されます。この場合のタスクは、ユーザーが特定の時点でどのページを編集するかを予測することです。 TGN のさまざまなバリエーションをベースライン メソッドと比較します。

Wikipedia データセット上の TGN のさまざまな構成が、Wikipedia データセット上の将来の接続を予測するための予測精度と時間の観点から既存の方法 (TGAT および Jodie) と比較されます。より多くの論文がこれら 2 つの重要な基準について厳密に報告することを期待します。

この区画化研究は、さまざまな TGN モジュールの重要性を示し、いくつかの一般的な結論を導き出すことを可能にします。まず、メモリは重要です。メモリ不足はパフォーマンスの大幅な低下につながる可能性があります[7]。 2 番目に、メモリ状態を直接出力するのではなく、埋め込みモジュールを使用することが重要です。グラフアテンションベースの埋め込みが最もパフォーマンスが良いようです。 3 番目に、メモリがあれば、1 ホップ近傍のメモリによってモデルが 2 ホップ近傍情報に間接的にアクセスできるようになり、グラフ アテンション レイヤーを 1 つだけ使用すれば十分になります (これにより計算時間が大幅に短縮されます)。

最後に、動的グラフでの学習は、多くの重要なアプリケーションと大きな潜在的影響を持つ、ほぼ新しい研究分野であると主張します。私たちの TGN モデルは、動的グラフの学習機能を改善し、これまでの結果を統合および拡張する上で重要な前進であると考えています。この研究分野が発展するにつれて、より優れた、より大きなベンチマークが重要になります。現在、Open Graph ベンチマークの一環として、新しい動的グラフ データセットとタスクの作成に取り組んでいます。