Meta AI Zeng Hanqing: サブグラフニューラルネットワークのスケーラブルなアプリケーションと表現力豊かなアプリケーション

ディープラーニングの活発な分野として、グラフニューラルネットワークは人工知能科学者から幅広い注目を集めています。グラフ理論とディープラーニングは密接に統合でき、グラフ上の位相情報も十分に活用できるため、グラフニューラルネットワークは、従来のディープラーニングの純粋ユークリッド空間における非ユークリッド空間の対称性と推移性を分析する問題を解決するためのアイデアを提供します。グラフ ニューラル ネットワークの開発は、さまざまな段階で 2 つの大きな課題に直面しています。一方、産業用アプリケーションにおけるグラフの大規模な特性により、グラフ上での従来の k-hop メッセージ パッシングは指数関数的増加の課題に直面しており、グラフ ニューラル ネットワークがグラフ上の詳細なトポロジ情報を取得する際の障害となっています。一方、従来のグラフニューラルネットワークでは、グラフ同型性テストとワイスファイラー・レーマンテストにおいてまだ改善の余地が残っています。

Meta AI 研究科学者の Zeng Hanqing 博士は、サブグラフ ネットワークの応用に関する徹底的な研究に基づいて、上記の 2 つの問題に対する新しい考え方を提案しました。一方では、異なるタスクでサブグラフの異なる意味をどのように開発するか、それによって大規模グラフの計算ボトルネックを減らし、元の GNN の表現力の上限を突破する方法です。元の画像を「縮小」してサブグラフを取得すると、サブグラフでトレーニングされた GNN は、大規模なフルグラフでトレーニングされた GNN に近似できます (モデルの一般化能力に基づく)。これから派生したサブグラフ サンプリングに基づく一連の作業により、トレーニングの計算/ストレージ コストが大幅に削減されました。一方、サブグラフを元のグラフのトポロジ情報の強化として考えると、サブグラフ内およびサブグラフ間でのメッセージの受け渡しなど、複数の観点から新しい GNN モジュールを設計して、モデルの表現力を高めることができます。古典的なグラフ同型性テスト問題では、サブグラフ GNN が理論的に最強のフルグラフ GNN を上回ります。

将来的には、高い効率性と高い表現力の両方をどのように実現するかが、サブグラフ GNN が解決する必要がある重要な問題として残ります。 Zeng 博士は、ノード分類とグラフ分類という 2 つのタスクでサブグラフ GNN のコア モジュールを組み合わせることで、計算オーバーヘッドと表現力のバランスを実現するアイデアを提供しました。

1. グラフニューラルネットワークの基礎知識

まず、従来のグラフ ニューラル ネットワークの概念、基本的なタスクと課題、上記の問題にサブグラフ ニューラル ネットワークを適用する基本的な考え方、およびサブグラフ ニューラル ネットワークとフルグラフ ニューラル ネットワークの比較を紹介します。

1. グラフニューラルネットワークとグラフ表現学習

グラフ表現学習タスクは、ノード レベルでの情報埋め込み、エッジ レベルでの情報埋め込み、グラフ レベルでの情報埋め込みに分けられます。ノード レベルでは、グラフの入力に基づいて各ポイントの埋め込みが生成されます。グラフレベルでは、ノード埋め込み情報をプールすることで、グラフレベルの埋め込み情報を取得できます。

2. サブグラフグラフニューラルネットワークとグラフニューラルネットワーク

① 相違点：サブグラフの違いは、トポロジ情報の取得、ノード特徴情報の抽出、メッセージの受け渡し、プーリング層などに反映されます。

②接続：サブグラフをグラフ全体の一部として計算することで生成された情報を、グラフ全体のニューラルネットワークの計算に適用することができます。

3. グラフニューラルネットワークの既存の問題

実際のデータ グラフの固有の特性により、従来のグラフ ニューラル ネットワークは、産業用アプリケーションでさまざまな問題、特にスケーラビリティと表現力の問題に直面することがよくあります。一方、産業用アプリケーションのグラフのノード数は、実験グラフ データのノード数よりもはるかに多いことがよくあります。その結果生じる計算の複雑さにより、フルグラフ ニューラル ネットワークをグラフ データの計算に実際に使用することが困難になることがよくあります。大規模なグラフデータに使用できるグラフニューラルネットワークの設計は、グラフニューラルネットワークにおいて解決すべき緊急の課題です。一方、グラフデータ内の異なるノードの情報を区別するために、グラフニューラルネットワークは、異なる類似ノードに対して異なるノード埋め込み情報を生成できる必要があります。ノードの分析では、メッセージパッシングに基づく従来のグラフニューラルネットワークの理論上の上限は 1-WL であることが証明されています。識別性の高いグラフニューラルネットワークをどのように設計するかも、グラフニューラルネットワークが直面する課題です。

4. 最近の活動

下の図は最近の研究の一部を示し、各論文の焦点を示しています。

2. サブグラフニューラルネットワークとスケーラビリティ

グラフニューラルネットワークの上記の課題に対して、Zeng博士はサブグラフニューラルネットワークの観点から自身の考えを提案しました。古典的なサブグラフ ニューラル ネットワーク アルゴリズム GraphSIANT の分析を通じて、サブグラフ ニューラル ネットワークのスケーラビリティ手法を分析します。

1. グラフトレーニング：小バッチトレーニング

元のグラフよりもデータ容量が小さいが元のグラフの特徴を保持するサブグラフに対してグラフ ニューラル ネットワークの計算を実行すると、元のグラフのトレーニングに近似しながら、グラフ ニューラル ネットワークのトレーニングの計算の複雑さを軽減できます。また、サブグラフ内のメッセージ送信用ノード数はノード総数より少ないため、サブグラフノード数を設定することで、サブグラフニューラルネットワークの隣接点数を一定の有効範囲に制限することができ、隣接ノードの指数関数的増加による計算複雑化を防ぐことができる。

2. GraphSAINT: サブグラフサンプリングに基づくユニバーサルグラフトレーニングアーキテクチャ

トレーニングにおけるミニバッチトレーニングのパフォーマンスは、サンプリング方法が小さなサンプルで元の画像の構造情報を取得できるという事実に基づいています。元の画像情報を表現できるサブ画像サンプリング方法をどのように設計するかが、小バッチトレーニングにおける重要な課題となっています。

Zeng 博士が提案した GraphSAINT フレームワークの最初のステップは、重要度ノード/エッジ サンプリング、ランダム ウォーク、およびそのバリエーションなどのサンプリング アルゴリズムに基づいてサブグラフをサンプリングすることです。 2 番目のステップでは、ニューラル ネットワークを使用してサブグラフを計算します。 GraphSAINT は、異なるサンプリング アルゴリズム間の差異の影響を軽減するために正規化を追加し、分散削減を使用して重要なサブグラフを抽出する機能を強化します。これにより、サブグラフ サンプリングの全体的な信頼性が向上し、ランダム サンプリングを使用した一般化機能が向上します。さらに、Cluster-GNN はサブグラフ ニューラル ネットワーク サンプリングのスキームとしても考えることができます。

要約すると、サブグラフ ニューラル ネットワークの最初の適用方法は、元の画像の情報を反映できる元の画像内のサブグラフをサンプリングするサンプリング方法を設計して、計算の複雑さを軽減し、フル グラフ ニューラル ネットワークと同様の計算結果を生成することです。

3. サブグラフニューラルネットワークと表現力

従来のグラフニューラルネットワークは、表現力の点で 1-WL の上限があることが証明されています。グラフに基づいてより多くの情報を生成し、それによってグラフニューラルネットワークの表現力を高めることができるネットワークをどのように設計するかも、グラフニューラルネットワークが解決すべき緊急の課題です。

1. グラフ表現におけるサブグラフの応用

グラフ ニューラル ネットワークの表現力を判断する鍵は、アルゴリズムが類似しているが異なる「通常のグラフ」を区別できるかどうかにあります。ゼン博士の意見では、サブグラフが導入されるときに重要な直感は、「正規グラフのサブグラフは必ずしも正規ではない」ということであり、グローバル（グラフ全体）の配置はローカル（サブグラフ）の非対称性によって破られるということです。したがって、このようなサブグラフで 1WL (および対応する GNN) を実行すると、2 つのグラフが構造的に同一ではないことを区別できます。

2. Shadow-GNN: サブグラフとノードの分類

GraphSAINT とは異なり、shaDow-GNN では、各サブグラフはグラフ全体のプロパティを表すのではなく、各ターゲット ノードの「指紋」として機能します。全体的なアーキテクチャは次のとおりです。各ターゲット ノードについて、その周囲の小さな近傍サブグラフを抽出します (ここでの「小さな」とは、数億のノードの完全なグラフ内の 200 ノードで構成されるサブグラフのことであり、これらの 200 ノードは、Personalized PageRank スコアまたはその他の方法でフィルター処理できます)。この小さなサブグラフには、ターゲット ノードの 1 ホップおよび 2 ホップの近傍の (小さな) 一部しか含まれない場合があります。ただし、この浅いサブグラフでは深い GNN (たとえば、5 層) を使用して、サブグラフの情報がモデルによって完全に吸収され、抽出されるようにします。 GNN レイヤーの数 (5 など) はサブグラフの深さ (2 など) に直接リンクされなくなったため、このモデルは分離されていると言えます。さらに拡張すると、各ターゲット ノードは複数の隣接サブグラフで記述できるため、複数の GNN がサブグラフの埋め込みを並列に抽出し、最終的にアンサンブルを通じてターゲット ノードの埋め込みを取得できます。

3. サブグラフニューラルネットワークとグラフ分類

（１）アイデア：従来のGNNのカーネルはすべての直接隣接ノードの情報を集約しますが、サブグラフGNNのカーネルはサブグラフ全体の複数の層の情報を集約します。

（２）ネストされたGNN：内部GNNはshaDow-GNNの動作に似ています。各ノードに対して近傍サブグラフが取得され、次にこのサブグラフ上で多層GNNが実行され、サブグラフ埋め込みが生成されます。外側の GNN は、すべての内側の GNN のサブグラフ埋め込みに対して別のグローバル プーリングを実行してグラフ全体の埋め込みを取得し、それによってグラフ全体の予測ラベルを生成します。 shaDow-GNN が 1WL の表現力を上回っているため、Nested GNN も 1WL を上回っています。

（３）GNN-AK： GNN-AKはカーネルの使用法をさらに拡張したNested GNNの派生モデルである。ネストされた GNN は、すべてのサブグラフ埋め込みをフルレイヤーで集約しますが、GNN-AK は複数のサブグラフ埋め込みを集約します。直感的に言えば、GNN-AK は複数の Nested GNN を積み重ねたもので、多層 Nested GNN と同等です。このようなモデルレベルの拡張により、表現力も向上します。理論的には、GNN-AK は 1WL を上回り、3WL では区別できない一部の画像を GNN-AK で区別できます。各ノードに対して特別な隣接サブグラフ、つまり k ホップ サブグラフを取ると、k が増加すると GNN-AK の表現力も向上します。これは、サブグラフが大きいほど多くの情報が含まれ、表現力が向上することを示しています。

（４）OSANとESAN：情報拡張： OSANのサブグラフ集合は、k個のノードから構成されるすべての可能なサブグラフとして定義される。このサブグラフは、1-WL の初期色を生成するために使用されます (GNN と 1WL は同等であるため、1WL の初期色を拡張することは、各 GNN ノードの初期機能を強化することと同等です)。各ノードと各 k 指定サイズのサブグラフが一致して、初期色のセットが生成されます。元の 1-WL (各ノードには初期色が 1 つだけあります) と比較すると、OSAN メッセージによって送信される情報はより豊富になります。また、k サイズのサブグラフには元のグラフの構造情報が含まれているため、サブグラフによって生成された新しい情報により、GNN はより豊富な構造情報を抽出することもできます。この式は、各 WL 反復で色を更新するプロセスを示しています。最初の式は元の WL に対応し、2 番目の式はサブグラフベースの WL に対応します。次のC(v, g)は、ここでのvの色もサブイメージgに依存することを意味します。

表現力の面では、k 値が増加するにつれて、OSAN の表現力が徐々に増加します。

もう 1 つの典型的なアプリケーションは ESAN です。サブグラフを使用して情報伝送の種類を増やします。

構築されたサブグラフ上での独立した情報受け渡しとは異なり、ESAN はサブグラフ間での情報受け渡しという新しい情報受け渡し操作を追加します。つまり、異なるグラフ上でニューラルネットワークの計算を同時に実行し、異なるサブグラフの同じ層の出力上で情報を統合して「サブグラフ間」の情報伝達を形成し、それによって情報伝達を豊かにするという目的を達成します。

(右: エッジ削除によるサブグラフ構築法: 元のグラフのすべてのエッジから 1 つのエッジを削除して得られるサブグラフが ESAN のサブグラフです。また、元のグラフからエッジを削除するさまざまな方法を示しています。)

IV. 今後の展望

1. 問題と解決策

同じ計算方法は、スケーラビリティと表現力の向上という点では矛盾した状態になることがよくあります。つまり、表現力が強いサブグラフ GNN は計算効率がよくありません。主な理由は、①GNNは多数のサブグラフを処理する必要があり、各サブグラフのサイズが大きく異なることです。 ②Kステップサブグラフに含まれるサブグラフとノードの数は、kの増加とともに指数関数的に増加します。 ③ノードが削除されたサブグラフの数は、グラフ全体のノードの数に等しくなります。 Zeng 博士が提案した解決策は、さらにサンプリングを行うこと、つまり、トレーニング用にサブグラフ セット内のデータの一部をサンプリングすることです。ただし、さらなるサンプリング中に表現力の損失を減らすには、さらなる研究が必要です。

グラフニューラルネットワークが直面する課題は、下流のタスクによって異なります。グラフ埋め込みタスクは、主に分子グラフなどの小さなグラフデータに使用されますが、ノード分類は、ソーシャルネットワークなどの大規模なグラフ計算に多く使用されます。したがって、グラフニューラルネットワークのスケーラビリティ問題を解決するには、さらなる努力が必要です。

2. 今後の展望

将来的には、shaDow-GNN を基本フレームワークとして使用し、ノード分類タスクとグラフ分類タスク用に設計されたさまざまなサブグラフ GNN と組み合わせて、ノード分類タスクにおける超大規模グラフの表現力とスケーラビリティのバランスをより良くすることができます。巨大なソーシャル ネットワークから小さなサブグラフを抽出し、その小さなサブグラフ上でグラフ分類問題用に設計されたサブグラフ GNN を実行できます。サブグラフ GNN は表現力は高いですが、計算コストも高くなります。このようにして、モデルの全体的な複雑さの要件（グラフ全体に対する線形複雑さ、小さなサブグラフに対する多項式複雑さ）に準拠しながら、shaDow-GNNの表現力を向上させることができます。