GraphSAGEグラフニューラルネットワークアルゴリズムの詳細な説明

GraphSAGE は 2017 年の論文ですが、その名前に含まれる 2 つのキーワード「帰納的」と「大規模グラフ」により、業界では常に高く評価されてきました。今日は、この記事の核となるアイデアと、見落とされがちな詳細を整理します。

GraphSAGE を使用する理由

まず、グラフがなぜ人気があるのか​​考えてみましょう。主な理由はいくつかあります。グラフには豊富なデータ ソースがあり、多くの情報が含まれています。そこで現在、グラフ内の情報をより有効に活用する方法を検討しています。

では、グラフで何をする必要があるのでしょうか?核となるのは、グラフの構造情報を使用して、各ノードに適した埋め込みベクトルを学習することです。適切な埋め込み結果があれば、次にどのような作業を行う場合でも、それらを直接使用してモデルを適合させることができます。

GraphSAGE 以前の主な手法としては DeepWalk と GCN がありましたが、グラフ全体を学習する必要があるという欠点がありました。これは主にトランスダクティブ学習に基づいており、トレーニング中は予測するノードがグラフにすでに含まれている必要があります。

実際のアプリケーションではグラフの構造が頻繁に変更されることを考慮すると、最終的な予測段階でグラフにいくつかの新しいノードが追加される可能性があります。それで何をすればいいのでしょうか? GraphSAGE はこの目的のために提案されました。その核となるアイデアは、実際には GraphSAGE = Graph Sample Aggregate という名前にあります。つまり、グラフをサンプリングして集計します。

GraphSAGEの背後にあるアイデア

サンプルと集計について言及しましたが、これらは具体的に何を意味するのでしょうか?このステップをどうやって行うのですか?なぜ大規模グラフに適用できるのでしょうか?次に、平易な言葉でわかりやすく説明します。

名前が示すように、サンプルはいくつかのポイントを選択することであり、集計はそれらの情報を集計することです。それで、全体のプロセスはどのように進むのでしょうか?下の写真をご覧ください。

まず、最初の図のサンプル プロセスを学習します。このようなグラフがあり、中央ノードで mebedding 更新を実行する必要があるとします。まず、その隣接ノードから S1 (この例では 3) ノードを選択します。K=2 の場合、2 番目のレイヤーを再度サンプリングします。つまり、選択した S1 隣接ノードの隣接ノードを選択します。

2 番目の図では、集約操作がわかります。つまり、最初に隣接ノードの隣接ノードを使用して隣接ノードの情報を更新し、次に更新された隣接ノードの情報を使用してターゲット ノード (中央の赤い点) を更新します。少し冗長に聞こえるかもしれませんが、考え方は複雑ではありません。よく考えれば理解できると思います。

3 番目の図では、未知のノードの情報を予測したい場合、その隣接ノードのみを使用して予測を行う必要があります。

この考えをもう一度整理してみましょう。シャオミンがどのような性格を持っているかを知りたい場合は、彼の親しい友人を数人見つけて観察し、さらに確認するために、彼の友人の別の友人を選んでもう一度観察します。つまり、シャオミンの友達を見れば、その友達がどんなタイプの人なのかが判断でき、その友達をもとに、シャオミンがどんな性格なのかを大まかに知ることができるのです。

GraphSAGEのアイデア

これでGraphSAGEの基本的な考え方はわかりましたが、まだ混乱しているかもしれません。単一ノードの考え方がこのようなものである場合、全体的なトレーニングプロセスはどのように実行すればよいのでしょうか。これまで、GraphSAGE がなぜ大規模グラフに適用できるのか、またなぜそれが帰納的であるのかについては説明されていません。

次に、GraphSAGE のトレーニング プロセスと、このプロセスにおける利点についていくつかの情報を追加します。

まず、初期の特徴から始めて埋め込みレイヤーをレイヤーごとに更新する必要があることを考慮すると、どのポイントを集約する必要があるかをどのように知るのでしょうか?上記のサンプルの考え方を適用して、アルゴリズムの具体的な方法を見てみましょう。

まず、アルゴリズムの 2 行目から 7 行目を見てください。これは実際にはサンプリング プロセスであり、サンプル結果は B に保存されます。次の 9 ～ 15 行は集約プロセスであり、前のサンプルの結果に従って、ターゲット ノードに対応する隣接情報を集約します。

注意深い友人は、サンプルプロセスが K から 1 まで (2 行目を参照)、集計プロセスが 1 から K まで (9 行目) であることに気付いたはずです。理由は明らかです。サンプリングを行うときは、まずグラフ全体から埋め込みたいノードを選択し、次にこれらのノードの近傍をサンプリングし、徐々により遠い近傍までサンプリングしていきます。

ただし、集約する場合は、まず最も遠い隣接ノードから開始し、最後に K 番目のレイヤーのターゲット ノードに集約する必要があります。これがGraphSAGEの完全なアイデアです。

そこで私たちが考えなければならないのは、このような単純なアイデアにはどんな謎があるのか​​ということです。

GraphSAGEの微妙な点

まず、なぜGraphSAGEを提案したのでしょうか?実は、最も重要なのは帰納的学習です。過去 2 日間、私はいくつかのディスカッション グループで学生たちがトランスダクティブ ラーニングとインダクティブ ラーニングについて議論しているのを見てきました。一般的に言えば、インダクティブ ラーニングはテスト中に新しく追加されたコンテンツについて間違いなく推論することができます。

したがって、GraphSAGE の主な利点の 1 つは、トレーニング後にグラフ ネットワークに新しく追加されたノードに対しても推論を実行できることであり、これは実際のアプリケーション シナリオで非常に重要です。

一方、グラフ ネットワークのアプリケーションでは、データ セットが非常に大きくなることが多いため、ミニ バッチ機能が非常に重要です。しかし、GraphSAGE の考え方により、他のノードを考慮せずにサンプリングしたデータのみを集計する必要があります。各バッチは、サンプル結果のバッチの組み合わせになります。

もう一度、集計関数について考えてみましょう。ここでのトレーニング結果では、集計関数が非常に重要な役割を果たしています。集計関数の選択に関しては、次の 2 つの条件があります。

まず、ターゲットの集計関数パラメータをトレーニングするために逆方向に転送する必要があるため、微分可能でなければなりません。

2 つ目は対称性です。ここでの対称性は、入力に対する鈍感性を意味します。集約すると、グラフ内のノード関係に連続的な特性がなくなるためです。

そのため、著者は原文で平均や最大プーリングなどのアグリゲータを選択しました。著者は LSTM も使用しましたが、ノードは入力前にシャッフルされていたため、LSTM はシーケンス順序から知識を学習できませんでした。

さらに、この論文には細かい点があります。私は最初にこの論文を読んだとき、注意深く読んでいませんでした。友人に指摘されて初めて、それが真実だと気づきました。原文は次のとおりです。

ここで、アルゴリズム 1 の 4 行目と 5 行目は、先ほど示したアルゴリズムの 11 行目と 12 行目です。

つまり、著者が記事で言及しているGraphSAGE-GCNは、実際には上記の集約関数を使用して、他の方法で最初に集約してから連結する操作を置き換えており、著者はこの方法が局所スペクトル畳み込みの線形近似であるため、GCNアグリゲータと呼ばれていると指摘しています。

掃除をしましょう

最後に、人気があり、比較的シンプルなものをいくつか追加してみましょう。 GraphSAGE は一般的にどのような用途に使用されますか?

まず著者は教師なし学習と教師あり学習の両方に使用できることを提案しています。教師あり学習では、最終的に予測された損失関数を直接ターゲットとして使用し、バックプロパゲーションを使用してトレーニングを行うことができます。教師なし学習はどうでしょうか?

実際、目的が何であれ、注目すべきはグラフ自体です。主に埋め込み操作を完了するためにグラフを使用します。つまり、ノードを埋め込むと、より効果的な特徴ベクトルが得られます。では、教師なし学習を行う場合、埋め込み結果が正しいか間違っているかをどのように判断すればよいのでしょうか?

著者は、隣人同士の関係という非常にわかりやすい考え方を選びました。デフォルトでは、2 つのノードが互いに近い場合、埋め込み結果は同様になります。距離が遠い場合、埋め込み結果は当然大きく異なります。これにより、次の損失関数が簡単に理解できるようになります。

z_v はターゲットノード u の隣接ノードであることを示し、v_n はそうではないことを示します。P_n(v) は負のサンプルの分布、Q は負のサンプルの数です。

では、残る唯一の疑問は、隣人をどのように定義するかということです。

著者は非常に単純なアイデアを選択しました。DeepWalk を直接使用して、ステップ長 5 でランダム ウォークを実行し、50 回テストすると、すべての近傍が見つかります。

要約する

実験結果は示しませんが、著者が多くの場所でいくつかのベースラインのアイデアを使用していることがわかります。ビジネスニーズに合わせて、対応する場所でそれらを置き換えたり調整したりできます。

今後もGNNと埋め込みに関する古典的で刺激的な論文をいくつか紹介していきます。引き続きご注目ください~~~