GNN初心者必読！ Google Research が、SOTA グラフ ニューラル ネットワークをゼロから構築する方法を教えます

[[422426]]

近年、ニューラル ネットワークは自然言語、画像、音声、その他のデータで大きな進歩を遂げ、モデルのパフォーマンスを前例のないレベルにまで引き上げましたが、グラフ データでどのようにトレーニングするかは依然として研究対象となっています。

従来のニューラル ネットワークに入力されるデータは通常、各サンプル間に関連性がありませんが、グラフ データはより複雑で、各ノード間に接続があり、現実世界のデータ保存方法とより一致しています。現実世界のオブジェクトは、多くの場合、他のオブジェクトとのつながりに基づいて定義されます。オブジェクトのセットとそのつながりは、自然にグラフとして表現できます。グラフ データに基づくニューラル ネットワークは、グラフ ニューラル ネットワーク (GNN) とも呼ばれます。

グラフニューラルネットワークの開発は徐々に注目を集めるようになり、推論や常識などの分野でも多くの成果を上げています。Google の研究者は最近、グラフニューラルネットワークの開発の歴史を紹介し、現代のグラフニューラルネットワークについて議論し説明するブログを公開しました。

グラフは頂点と辺で構成されています。ソーシャルネットワークなどのデータは、人間の頭の中では自然にグラフとして表現できます。しかし、画像やテキストをグラフとして表現する方法について考えたことはありますか?

画像は通常、チャネルを持つ長方形のグリッドとして考えられ、たとえば 244x244x3 の 3 次元マトリックスとして表されます。

画像を別の方法で考えると、画像は規則的に構造化された画像であり、各ピクセルがノードを表し、エッジを介して隣接するピクセルに接続されていると言えます。境界以外の各ピクセルには 8 個の隣接ノードがあり、各ノードに格納される情報はピクセルの RGB 値を表す 3D ベクトルです。

グラフの接続性を視覚化する 1 つの方法は、隣接行列です。これらのノードを並べ替えます。5x5 の画像には 25 ピクセルあり、2 つのノード間にエッジがある場合は隣接行列にエントリがある行列を構築します。

テキストの場合、各文字、単語、またはトークンにインデックスを関連付け、各文字またはインデックスがノードであり、エッジによって次のノードに接続される有向グラフとしてテキストを表すことができます。

ただし、実際の使用では、テキストや画像は通常、このようにエンコードされません。すべての画像とテキストは非常に規則的な構造を持っているため、グラフで表現するのは冗長なステップです。たとえば、画像の隣接行列は、すべてのノードまたはピクセルが接続され、グリッド構造に含まれているため、通常はリボンのような構造になります。テキストの隣接行列は、各単語が前の単語と次の単語にのみ接続されているため、1 本の対角線のみで構成されます。

ニューラルネットワークを使用してグラフタスクを表現する場合、最も重要な表現の1つはその接続性です。隣接行列は良い選択ですが、前述のように、隣接行列は疎すぎて、スペースの利用率が高くありません。もう1つの問題は、同じグラフの隣接行列を表現する方法が複数あり、ニューラルネットワークはこれらの隣接行列の出力結果が同じであることを保証できない、つまり順列不変ではないことです。

また、異なる形状のグラフに同じ隣接行列が含まれる場合もあります。

疎行列を表現するエレガントかつ効率的な方法は、隣接リストです。これらは、隣接リストの k 番目のエントリのタプル (i, j) としてノード間のエッジの接続性を記述します。エッジの数は隣接行列のエントリ数よりもはるかに少ないため、グラフの切断された部分 (エッジのない部分) での計算と保存を回避できます。

グラフは順列不変行列形式で記述されるため、グラフニューラルネットワーク (GNN) を使用してグラフ予測タスクを解決できます。 GNN は、グラフのすべての属性 (ノード、エッジ、グローバル コンテキスト) を最適化可能な変換であり、グラフの対称性 (順列不変性) を維持できます。 GNN は「グラフイン、グラフアウト」アーキテクチャを採用しています。つまり、これらのモデル タイプはグラフを入力として受け入れ、そのノード、エッジ、およびグローバル コンテキストに情報をロードし、入力グラフの接続性を変更せずにこれらの埋め込みを段階的に変換します。

最も単純な GNN モデル アーキテクチャでは、グラフの接続性がまだ使用されていません。グラフの各コンポーネントに個別の多層パーセプトロン (MLP) (他の微分可能モデルも可能) を使用することを GNN レイヤーと呼ぶことができます。

各ノード ベクトルに対して、MLP を使用して学習可能なノード ベクトルを返します。各エッジに対して同じことを行い、各エッジの埋め込みを学習します。また、グローバル コンテキスト ベクトルに対しても同じことを行い、グラフ全体の単一の埋め込みを学習します。

ニューラル ネットワーク モジュールやレイヤーと同様に、これらの GNN レイヤーを積み重ねることができます。

GNN は入力グラフの接続性を更新しないため、GNN の出力グラフは、入力グラフと同じ隣接リストと同じ数の特徴ベクトルを使用して記述できます。

シンプルな GNN を構築した後、次のステップは、上記のタスクで予測を行う方法を検討することです。

まずバイナリ分類のケースを検討しますが、このフレームワークはマルチ分類や回帰のケースにも簡単に拡張できます。タスクがグラフ ノードに対してバイナリ分類予測を行うことであり、グラフにすでにノード情報が含まれている場合は、各ノード埋め込みに線形分類器を適用できます。

実際の状況はより複雑である可能性があり、たとえば、グラフ内の情報はエッジに格納され、ノードには情報がないが、ノードの予測は依然として必要である可能性があります。したがって、エッジから情報を収集し、それを予測のためにノードに提供する方法が必要です。

これはプーリングを通じて実現できます。プーリングは 2 つのステップで実行されます。プールされる各項目について、それぞれの埋め込みを収集し、それらを連結してマトリックスにします。通常は、収集された埋め込みを合計演算によって集計します。

GNN レイヤー内でプーリングを使用して、学習した埋め込みがグラフの接続性をより意識するようにすることで、より複雑な予測を行うことができます。これはメッセージ パッシングを使用して実行できます。メッセージ パッシングでは、隣接するノードまたはエッジが情報を交換し、互いの更新された埋め込みに影響を与えます。

メッセージングは​​次の 3 つのステップで構成されます。

1. グラフ内の各ノードについて、隣接するノードの埋め込み (またはメッセージ) をすべて収集します。

2. 集計関数 (sum など) を使用してすべてのメッセージを集計します。

3. 集約されたすべてのメッセージは、更新関数（通常は学習されたニューラル ネットワーク）を介して渡されます。

これらの手順は、グラフの接続性を活用するための鍵であり、GNN レイヤーでより複雑なメッセージ パッシング バリアントを構築して、より表現力豊かな GNN モデルを作成することもできます。

本質的に、メッセージ パッシングと畳み込みは、要素の隣接情報を集約して処理し、要素の値を更新する操作です。グラフでは要素はノードであり、画像では要素はピクセルです。ただし、各ピクセルの隣接要素の数が固定されている画像とは異なり、グラフ内の隣接ノードの数は可変です。 GNN レイヤーに渡されたメッセージを積み重ねることで、ノードは最終的にグラフ全体からの情報を組み込むことができます。

ノードが埋め込みを学習した後の次のステップはエッジです。実際のシナリオでは、データセットには必ずしもすべての種類の情報 (ノード、エッジ、グローバル コンテキスト) が含まれているわけではありません。ユーザーがノードの予測を行いたいが、提供されたデータセットにはエッジ情報しかない場合、プーリングを使用してエッジからノードに情報をルーティングする方法を示しますが、これはモデルの最後の予測ステップに限定されます。これに加えて、メッセージ パッシングを使用して、GNN レイヤー内のノードとエッジ間で情報を共有することもできます。

隣接エッジからの情報は、以前に隣接ノード情報を使用したのと同じ方法でマージできます。最初にエッジ情報をマージし、更新関数を使用して変換して保存します。

ただし、グラフに格納されているノードとエッジの情報は必ずしも同じサイズや形状ではないため、現時点ではそれらを組み合わせる明確で効果的な方法はありません。より良いアプローチは、エッジ空間からノード空間へ、およびその逆の線形マッピングを学習することです。あるいは、更新関数の前にそれらを連結することもできます。

最後のステップは、グローバル ノードとエッジの表現を取得することです。

前述のネットワークには欠陥があります。メッセージ パッシングを複数回適用しても、グラフ内で直接接続されていないノードは、互いに情報を効果的に渡すことができない可能性があります。ノードの場合、ネットワークの層が k 層あると、情報は最大 k ステップで伝播します。

これは、予測タスクが遠く離れたノードまたはノードのグループに依存する状況では問題になる可能性があります。 1 つの解決策は、すべてのノードが互いに情報を渡すことができるようにすることです。残念ながら、大きなグラフの場合、計算コストは​​非常に高くなりますが、小さなグラフには使用できます。

この問題の解決策の 1 つは、グラフのグローバル表現 (U) を使用することです。これは、マスター ノードまたはコンテキスト ベクトルと呼ばれることもあります。このグローバル コンテキスト ベクトルは、ネットワーク内の他のすべてのノードとエッジに接続されており、それらの間で情報を渡すブリッジとして機能し、グラフ全体の表現を構築します。これにより、他の方法よりも豊富で複雑なグラフ表現を作成できます。

この観点から見ると、すべてのグラフ属性はすでに表現を学習しているため、関心のある属性の情報を残りの属性と比較して調整することで、プーリングで活用できます。たとえば、ノードの場合、隣接ノードの情報、接続されたエッジ、およびグローバル情報を考慮することができます。これらすべての可能性のある情報ソースに新しいノードを埋め込むには、それらを単純に接続します。さらに、線形投影と特徴ごとの変調レイヤーを適用することで、同じ空間にマッピングすることもできます。

上記のプロセスを通じて、単純な GNN がどのようにして sota モデルに発展するかを皆さんは理解できたと思います。グラフのノードとエッジの表現を取得したら、後続のタスク用に別のネットワークを設計できます。GNN は、ニューラル ネットワークがグラフ データを処理する方法を提供します。

元のブログには、GNN の実際のケースとデータセットもいくつか含まれており、それらにおける GNN の具体的な役割が理解できます。さらに詳しく知りたい場合は、参照リンクにアクセスして読んでください。