GCN グラフ畳み込みネットワークの紹介

この記事では、GCN と呼ばれるよく知られたグラフ ニューラル ネットワークについて詳しく説明します。まず、それがどのように機能するかを直感的に理解し、次にその背後にある数学を詳しく見ていきましょう。

グラフを使用する理由

多くの問題は本質的にグラフです。私たちの世界では、分子、ソーシャル ネットワーク、論文引用ネットワークなど、多くのデータがグラフとして見られます。

グラフ上のタスク

• ノード分類: 特定のノードのタイプを予測します。
• リンク予測: 2つのノードが接続されているかどうかを予測する
• コミュニティ検出: 密に接続されたノードのクラスターを識別します。
• ネットワークの類似性: 2 つの (サブ) ネットワークはどの程度類似していますか?

機械学習のライフサイクル

グラフには、ノード機能 (ノードを表すデータ) とグラフの構造 (ノードの接続方法を表す) があります。

ノードについては、各ノードのデータを簡単に取得できます。しかし、グラフの構造に関しては、そこから有用な情報を抽出するのは簡単な作業ではありません。たとえば、2 つのノードが互いに非常に近い場合、他のノードのペアとは異なる方法で処理する必要がありますか? 高次ノードと低次ノードをどのように処理すればよいですか? 実際、特定のタスクごとに、特徴エンジニアリング、つまりグラフ構造を特徴に変換するだけで、多くの時間とエネルギーが消費されます。

何らかの方法でグラフのノード機能と構造情報の両方を入力として取得し、どの情報が有用であるかをマシンが自ら判断できるようになれば、さらに良いでしょう。

これがグラフ表現学習が必要な理由です。

グラフ畳み込みニューラルネットワーク (GCN)

論文：グラフニューラルネットワークに基づく半教師あり分類（2017）[3]

GCN は、グラフ上で直接動作し、グラフの構造情報を活用する畳み込みニューラル ネットワークです。

これは、ごく一部のノードにのみラベルが付いているグラフ (引用ネットワークなど) 内のノード (ドキュメントなど) を分類する問題 (半教師あり学習) に対処します。

グラフ上の半教師あり学習の例。一部のノードにはラベルがありません (不明なノード)。

本旨

「畳み込み」という名前が示すように、このアイデアは画像から生まれ、グラフに導入されました。ただし、画像の構造は固定されているのに対し、グラフははるかに複雑です。

GCN の基本的な考え方は、各ノードについて、そのノード自身の特徴を含むすべての隣接ノードからその特徴情報を取得するというものです。 average() 関数を使用するとします。すべてのノードに対して同じことを行います。最後に、計算された平均値をニューラル ネットワークに入力します。

下の図は、引用ネットワークの簡単な例を示しています。各ノードは研究論文を表し、エッジは引用を表します。ここで前処理のステップがあります。ここでは、元の論文を特徴として使用せず、代わりに論文をベクトルに変換します（tf-idf などの NLP 埋め込みを使用）。 NLP 埋め込み (TF-IDF など)。

緑のノードを考えてみましょう。まず、ノード自体を含むすべての隣接ノードの固有値を取得し、平均を取ります。最後に、結果ベクトルがニューラル ネットワークを通じて返され、最終結果として使用されます。

GCNの主なアイデア。緑のノードを例に挙げてみましょう。まず、自身のノードを含むすべての隣接ノードの平均を取得します。次に、平均値がニューラル ネットワークに渡されます。 GCN では、完全に接続されたレイヤーを 1 つだけ使用することに注意してください。この例では、出力として 2D ベクトル (完全接続層内の 2 つのノード) を取得します。

実際の操作では、平均関数よりも複雑な集計関数を使用できます。より多くのレイヤーを積み重ねて、より深い GCN を取得することもできます。各レイヤーの出力は次のレイヤーの入力として扱われます。

2 層 GCN の例: 最初の層の出力は 2 番目の層の入力になります。また、GCNのニューラルネットワークは完全に接続された層にすぎないことにも注意してください（画像は[2]から）。

これがどのように機能するかを数学的に詳しく見てみましょう。

直感とその背後にある数学

まず、注釈が必要です

以下に示すグラフ G を考えます。

グラフ G から、隣接行列 A と次数行列 D が得られます。特徴行列Xもあります。

では、各ノードの固有値をその隣接ノードからどのように取得できるでしょうか? 答えは、A と X を掛け合わせることにあります。

隣接行列の最初の行を見ると、ノード A とノード E の間に接続があることがわかります。結果の行列の最初の行は、A に接続されたノード E の固有ベクトルです (以下に示すように)。同様に、得られた行列の2行目は、DとEの固有ベクトルの合計です。この方法により、すべての隣接ノードのベクトルの合計を取得できます。

合計ベクトル行列 AX の最初の行を計算します。

ここはまだ改善の余地があります。

• ノード自体の特性は無視します。たとえば、計算されたマトリックスの最初の行には、ノード A の特徴も含まれている必要があります。
• sum() 関数を使用する代わりに、隣接ノードの特徴ベクトルの平均、またはさらに良い方法としては加重平均を取る必要があります。では、なぜ sum() を使用しないのでしょうか。その理由は、sum() を使用すると、次数が大きいノードは大きな v ベクトルを生成する可能性が高く、次数の小さいノードは小さなクラスター化されたベクトルを取得する傾向があり、後で勾配爆発や勾配消失を引き起こす可能性があるからです (たとえば、シグモイドを使用する場合)。さらに、ニューラル ネットワークは入力データのサイズに敏感であるようです。したがって、起こりうる問題を排除するために、これらのベクトルを正規化する必要があります。

問題(1)では、単位行列IをAに加えて新しい隣接行列Ãを得ることで解くことができます。

lambda=1 とすると (ノード自体の特徴をその隣接ノードの特徴と同じくらい重要にする)、Ã=A+I となります。lambda をトレーニング可能なパラメータとして扱うことができますが、ここでは lambda に 1 を割り当てるだけでよいことに注意してください。論文でも、lambda は単に 1 に割り当てられています。

問題（2）の場合：行列のスケーリングでは、通常、行列に対角行列を掛けます。今回のケースでは、集約された特徴の平均を取る、つまり数学的に言えば、集約ベクトル行列 ÃX をノード次数に応じてスケーリングすることになります。直感的に、ここでスケーリングに使用される対角行列は、次数行列 D̃ に関連するものであることがわかります (なぜ D ではなく D̃ なのでしょうか? A ではなく、新しい隣接行列 Ã の次数行列 D̃ を考慮しているためです)。

ここで問題になるのは、合計ベクトルをどのようにスケーリング/正規化するかということです。言い換えると、

近隣ノードに関する情報を特定のノードに渡すにはどうすればよいでしょうか。まずは、古くからある平均から始めます。この場合、D̃の逆行列（つまり、D̃^{-1}）が作用します。基本的に、D̃ の逆行列の各要素は、対角行列 D の対応するエントリの逆になります。

たとえば、ノード A の次数は 2 なので、ノード A の集約ベクトルを 1/2 倍にし、ノード E の次数は 5 なので、E の集約ベクトルを 1/5 倍にする、というようになります。

したがって、D̃を否定してXを掛けると、すべての隣接ノード（自身のノードを含む）の特徴ベクトルの平均を取ることができます。

ここまでは順調ですね。しかし、加重平均() についてはどうなのかと疑問に思うかもしれません。直感的には、高次ノードと低次ノードを別々に扱う方がよいはずです。

新しいスケーリング方法により、「加重」平均が得られます。ここで行っているのは、高次ノードの影響を減らすために、低次ノードに重み付けをすることです。この加重平均の背後にある考え方は、低次数のノードは隣接ノードに大きな影響を与える一方で、高次数のノードは影響が多くの隣接ノードに分散されるため、影響が低くなると想定することです。

ノード B で隣接ノード機能を集約する場合、ノード B 自体に最大の重み (次数 3) を割り当て、ノード E に最小の重み (次数 5) を割り当てます。

2回正規化したので、「-1」を「-1/2」に変更しました。

たとえば、10 クラスの多重分類問題があり、F が 10 に設定されているとします。 2 番目のレイヤーに 10 次元のベクトルを作成した後、ソフトマックス関数を使用してこれらのベクトルを予測します。

損失関数の計算方法は非常に簡単で、すべてのラベル付き例のクロスエントロピー誤差を計算することです。ここで、Y_{l} はラベル付きノードのセットです。

レイヤー数

#レイヤーの意味

レイヤーの数は、ノード機能が送信できる最大距離を示します。たとえば、1 層の GCN では、各ノードは隣接ノードからのみ情報を取得できます。各ノードの情報収集プロセスは、すべてのノードに対して独立して同時に実行されます。

最初のレイヤーの上に別のレイヤーを追加するときは、情報収集のプロセスを繰り返しますが、今回は、隣接ノードにはすでに隣接ノードに関する情報があります (前のステップから)。これにより、レイヤーの数は、各ノードが実行できるホップの最大数になります。したがって、ノードがネットワークからどの程度遠くまで情報を取得すべきかに応じて、#layers に適切な数を設定できます。しかし、グラフでは通常、行き過ぎは望ましくありません。 6 ～ 7 ホップでグラフのほぼ全体を取得できますが、これにより集約の意味は薄れます。

GCN は何層に積み重ねるべきですか?

この論文では、著者らはそれぞれ浅い GCN と深い GCN に関するいくつかの実験も行いました。下の図では、2 層または 3 層のモデルを使用すると最良の結果が得られることがわかります。さらに、深い GCN (7 層以上) の場合、パフォーマンスが低下することがよくあります (青い破線)。 1 つの解決策は、隠し層間の残差接続 (紫色の線) を使用することです。

きちんとメモを取る

• GCN はグラフ上の半教師あり学習に使用されます。
• GCNはノードの特徴と構造の両方を使用してトレーニングされる
• GCN の主なアイデアは、すべての隣接ノード機能 (自身のノードを含む) の加重平均を取ることです。次数が低いノードには大きな重みが与えられます。その後、得られた特徴ベクトルをニューラル ネットワークを通じてトレーニングします。
• より多くのレイヤーを積み重ねて、GCN をさらに深くすることができます。深い GCN 内の残余接続を考慮してください。通常、2 層または 3 層の GCN を選択します。
• 数学の注意: 対角行列を見るときは、行列のスケーリングについて考えます。
• 以下はStellarGraphライブラリ[5]を使用したGCNデモです。リポジトリには、他の多くの GNN アルゴリズムも用意されています。

著者からのメモ

このフレームワークは現在、無向グラフ (重み付きまたは重みなし) に制限されています。ただし、元の有向グラフを無向 2 端子グラフとして表現し、元のグラフのエッジを表すノードを追加することで、有向エッジとエッジ機能を処理できます。

次は何ですか？

GCN の場合、ノード機能とグラフの構造の両方を活用できるようです。しかし、グラフ内のエッジが異なるタイプの場合はどうなるでしょうか? それぞれの関係を別々に扱う必要がありますか? この場合、隣接ノードをどのように集約すればよいでしょうか? 最近の高度な方法にはどのようなものがありますか?

グラフシリーズの次の記事では、さらに複雑な方法をいくつか見ていきます。

エッジのさまざまな関係（兄弟、友人など）をどのように処理しますか?