【E資格まとめ】グラフニューラルネットワーク（Graph Neural Network: GNN）

このシリーズではE資格対策として、シラバスの内容を項目別にまとめています。

E資格まとめ

試験概要ディープラーニングの理論を理解し、適切な手法を選択して実装する能力や知識を有しているかを認定する。１．応用数学（１）確率・統計（２）情報理論２．機…

1. グラフニューラルネットワーク（Graph Neural Network: GNN）
1.1. グラフニューラルネットワークの概要
1.2. グラフ畳み込みネットワーク（Graph Convolutional Network: GCN）
1.3. GraphSAGE（Graph Sample and Aggregrate）
1.4. GAT（Graph Attention Network）
2.

グラフニューラルネットワーク（Graph Neural Network: GNN）

グラフニューラルネットワークの概要

グラフニューラルネットワーク（Graph Neural Network: GNN）は、グラフデータを処理するためのディープラーニング手法です。GNNは各ノードが他のノードとの関係を学習する能力を持っています。これはソーシャルネットワーク、化学構造、プログラムの依存関係など、リアルワールドの多くのデータがグラフとして表現可能であることから非常に重要です。

GNNはノードとエッジから成るグラフ上で動作します。各ノードは特徴ベクトルによって表され、エッジはノード間の関係を表します。GNNは局所的な情報と隣接するノードからの情報を組み合わせて、各ノードの新しい特徴を学習します。これにより、GNNはノード間の複雑なパターンを捉えることができます。

グラフニューラルネットワークの基本的な動作は以下の通りです。まず、各ノードの特徴ベクトルが初期化されます。次に、各ノードは隣接するノードの特徴から情報を収集し、自身の新しい特徴を計算します。これは”メッセージパッシング”とも呼ばれます。このプロセスが一定の反復回数または収束条件まで行われます。

このプロセスを数式で表現すると、以下のようになります。

ノード v の新しい特徴ベクトル h_v^{(l)} は次のように計算されます：

$$ h_v^{(l)} = \text{ReLU} \left( \sum_{u \in \text{Nbr}(v)} \text{AGGREGATE}\left(h_u^{(l-1)}, h_v^{(l-1)}\right) \right) $$

具体的な問題に応じて、様々なバリエーション（GCN, GraphSAGE, GATなど）が存在します。

グラフ畳み込みネットワーク（Graph Convolutional Network: GCN）

グラフ畳み込みネットワーク（Graph Convolutional Network: GCN）は、グラフ上での畳み込みを行うニューラルネットワークの一種です。GCNは、グラフのノード間の接続性や各ノードの特徴を考慮して、より高度な特徴を学習することができます。一般的な畳み込みニューラルネットワークが画像データなどのグリッド状のデータに対して適用されるのに対し、GCNは構造的に複雑なグラフデータに対して適用されます。

GCNの重要な特徴は「畳み込み」です。ノードの特徴ベクトルがその隣接ノードからの情報を取り入れることにより更新されます。そして、各ノードはその隣接ノードの情報を「畳み込む」ことで、自身の新たな特徴ベクトルを生成します。これは、「メッセージパッシング」の形式をとります。

GCNの基本的な計算ステップは次のようになります：

集約ステップ：各ノードはその隣接ノードから特徴ベクトルを集約します。つまり、隣接ノードの特徴ベクトルをすべて足し合わせます。これはグラフ上での情報の伝播を表しています。
変換ステップ：集約された特徴ベクトルに重み行列を掛けて変換を行います。そして、非線形の活性化関数を適用します。

GCNでのノードの特徴更新の数式は以下の通りです：

$$ h_v^{(l)} = \sigma \left( W^{(l)} \sum_{u \in \text{Nbr}(v)} \frac{1}{\sqrt{d_v d_u}} h_u^{(l-1)} \right) $$

これらのステップが反復的に行われることで、GCNはノード間の関係を捉えながらグラフ全体の特徴を学習します。

GraphSAGE（Graph Sample and Aggregrate）

GraphSAGE（Graph Sample and Aggregrate）もまた、グラフニューラルネットワークの一種です。GraphSAGEの主な特徴は、入力として与えられたグラフから情報を学習し、それを用いて、未知のノード（つまり、学習時には存在しなかったノード）の特性を推定することができる点です。これは「誘導的学習」（inductive learning）と呼ばれる手法で、グラフデータに対する強力な学習能力を持ちます。

GraphSAGEの基本的なアルゴリズムは次の3ステップで構成されています：

ノードのサンプリング：ノードの近傍から固定数のノードをサンプリングします。このステップでは、全ての近傍ノードを考慮する代わりに、一部の近傍ノードのみをランダムに選び出します。これにより、計算量を大幅に削減することが可能になります。
特徴の集約：サンプリングした近傍ノードの特徴を集約します。集約関数は、平均（mean）、最大値（max）、またはLSTMなどを用いて定義することができます。
特徴の更新：集約した近傍の特徴と対象ノード自身の特徴を結合し、全結合層（Dense layer）を用いて新たな特徴に更新します。

この3ステップを複数のレイヤーに渡って繰り返すことで、GraphSAGEは各ノードの特徴をその近傍の情報を用いて更新します。

GraphSAGEでのノードの特徴更新の数式は以下の通りです：

$$ h_v^{(l)} = \sigma \left( W^{(l)} \cdot \text{CONCAT} \left( h_v^{(l-1)}, \text{AGGREGATE}(\{h_u^{(l-1)}: u \in \text{Nbr}(v)\}) \right) \right) $$

これらのステップにより、GraphSAGEはグラフ上で局所的な情報を効率的に集約し、各ノードの特徴を更新します。また、未知のノードに対してもその特徴を推定することができます。

GAT（Graph Attention Network）

GAT（Graph Attention Network）はグラフニューラルネットワークの一種で、ノードの特徴を更新する際に「注意機構」（attention mechanism）を用いています。各ノードは自身の近傍ノードの情報を集約しますが、その際に全ての近傍ノードの情報を同等に扱うのではなく、それぞれの近傍ノードへの「注意度」に基づいて情報を重み付けします。これにより、重要な近傍ノードからの情報に対しては大きな重みを、それ以外のノードからの情報に対しては小さな重みを付けるように学習します。

GATの基本的なアルゴリズムは以下のステップで構成されています：

注意度の計算：各ノードは自身と各近傍ノードとの間の注意度を計算します。これは、対象ノードと近傍ノードの特徴ベクトルを結合し、全結合層を通すことで行います。そして、注意度はソフトマックス関数を通すことで正規化されます。
特徴の集約：近傍ノードの特徴ベクトルを注意度で重み付けし、その結果を集約します。
特徴の更新：集約した近傍の特徴と対象ノード自身の特徴を結合し、全結合層を用いて新たな特徴に更新します。

GATでのノードの特徴更新の数式は以下の通りです：

$$ h_v^{(l)} = \sigma \left( \sum_{u \in \text{Nbr}(v)} \alpha_{vu}^{(l)} W^{(l)} h_u^{(l-1)} \right) $$

GATは注意機構を利用することで、各ノードがどの近傍ノードからの情報に注目すべきかを学習し、その結果、より精度の高いグラフ上での予測が可能となります。

最後までご覧いただきありがとうございました。