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

グラフニューラルネットワーク（GNN ）は、グラフとして表現できるデータを処理するための人工ニューラルネットワークの一種です。^{[1] [2] [3] [4] [5]}

より一般的な「幾何学的ディープラーニング」というテーマでは、既存のニューラルネットワークアーキテクチャの一部は、適切に定義されたグラフ上で動作するGNNとして解釈できます。 ^[6]コンピュータービジョンの文脈では、畳み込みニューラルネットワーク層は、ノードがピクセルであり、隣接するピクセルのみがグラフ内のエッジで接続されているグラフに適用されるGNNと考えることができます。自然言語処理のトランスフォーマー層は、ノードが自然言語テキストの文章内の単語またはトークンである完全なグラフに適用されるGNNと考えることができます。

GNNの重要な設計要素は、ペアワイズメッセージパッシングの使用であり、グラフノードは隣接するノードと情報を交換することで表現を反復的に更新します。いくつかのGNNアーキテクチャが提案されており、^{[2] [3] [7] [8] [9]}さまざまなタイプのメッセージパッシングを実装しており、^{[6] [10]再帰的[2]}または畳み込み構成的^[3]アプローチ から始まりました。2022年現在^[update]、メッセージパッシングを「超える」GNNアーキテクチャを定義できるかどうか、または代わりにすべてのGNNが適切に定義されたグラフ上のメッセージパッシングに基づいて構築できるかどうかは未解決の問題です。^[11]

GNNの関連する応用分野としては、自然言語処理、^[12] ソーシャルネットワーク、^[13] 引用ネットワーク、^[14] 分子生物学、^[15]化学、^{[16] [17]} 物理学^[18]およびNP困難な 組合せ最適化問題^[19]などがある。

GNNを実装するオープンソース ライブラリには、PyTorch Geometric ^[20] ( PyTorch )、TensorFlow GNN ^[21] ( TensorFlow )、Deep Graph Library ^[22] (フレームワークに依存しない)、jraph ^[23] ( Google JAX )、GraphNeuralNetworks.jl ^[24] /GeometricFlux.jl ^[25] ( Julia、Flux )などがあります。

一般的なGNNのアーキテクチャは、以下の基本レイヤーを実装しています。^[6]

1. 順列等変:順列等変層は、グラフの表現を同じグラフの更新された表現にマッピングします。文献では、順列等変層はグラフノード間のペアワイズメッセージパッシングによって実装されています。 ^{[6] [11]}直感的に、メッセージパッシング層では、ノードはすぐ隣から受信したメッセージを集約することによって表現を更新します。そのため、各メッセージパッシング層は、GNNの受容野を1ホップずつ増加させます。
2. ローカルプーリング：ローカルプーリング層は、ダウンサンプリングによってグラフを粗くします。ローカルプーリングは、畳み込みニューラルネットワークのプーリング層と同様に、GNNの受容野を拡大するために使用されます。例としては、k近傍プーリング、トップkプーリング^[26]、自己注意プーリング^{[27]などがあります。}
3. グローバルプーリング：グローバルプーリング層（読み出し層とも呼ばれる）は、グラフ全体の固定サイズの表現を提供します。グローバルプーリング層は、グラフのノードとエッジの順序の順列によって最終出力が変更されないように、順列不変である必要があります。^[28]例としては、要素ごとの合計、平均、最大値などがあります。

GNNはワイスファイラー・レマングラフ同型性テストよりも表現力が高くないことが実証されています。^{[29] [30]}実際には、これはGNNでは区別できない異なるグラフ構造（たとえば、同じ原子だが異なる結合を持つ分子）が存在することを意味します。単体複合体などの高次元ジオメトリで動作する、より強力なGNNを設計することができます。^{[31] [32] [10]} 2022年現在、将来のアーキテクチャがメッセージパッシングプリミティブを克服するかどうかは未解決の研究課題です。^[11][update]

メッセージパッシング層は、グラフを同じグラフの更新された表現にマッピングする順列等変層です。正式には、メッセージパッシングニューラルネットワーク（MPNN）として表現できます。^[6]

をグラフ、をノード集合、をエッジ集合とする。をあるノードの近傍とする。さらに、 をノードの特徴、 をエッジ の特徴とする。 MPNN層は次のように表現できる: ^[6]${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle N_{u}}$${\displaystyle u\in V}$${\displaystyle \mathbf {x} _{u}}$${\displaystyle u\in V}$${\displaystyle \mathbf {e} _{uv}}$${\displaystyle (u,v)\in E}$

${\displaystyle \mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)}$

ここで、 およびは微分可能関数（例：人工ニューラル ネットワーク）であり、 は任意の数の入力（例：要素ごとの合計、平均、または最大）を受け入れることができる順列不変の集約演算子です。特に、 およびはそれぞれ更新関数とメッセージ関数と呼ばれます。直感的には、MPNN 計算ブロックでは、グラフ ノードは隣接ノードから受信した メッセージを集約することによって表現を更新します。${\displaystyle \phi }$${\displaystyle \psi }$${\displaystyle \bigoplus }$ ${\displaystyle \phi }$${\displaystyle \psi }$

1 つ以上の MPNN レイヤーの出力は、グラフ内の各ノードのノード表現です。ノード表現は、ノード/グラフ分類やエッジ予測 など、あらゆる下流タスクに使用できます。${\displaystyle \mathbf {h} _{u}}$${\displaystyle u\in V}$

MPNN のグラフ ノードは、すぐ隣のノードから情報を集約して表現を更新します。そのため、MPNN レイヤーを積み重ねるということは、1 つのノードが最大で「ホップ」離れたノードと通信できることを意味します。原則として、すべてのノードが他のすべてのノードから情報を受信することを保証するには、グラフの直径に等しい数の MPNN レイヤーを積み重ねる必要があります。ただし、多くの MPNN レイヤーを積み重ねると、オーバースムージング^{[33]やオーバースカッシング[34]}などの問題が発生する可能性があります。オーバースムージングとは、ノード表現が区別できなくなる問題を指します。オーバースカッシングとは、長距離の依存関係を固定サイズの表現に押し込むことによって作成されるボトルネックを指します。スキップ接続^{[8] [35]} (残差ニューラル ネットワークなど)、ゲート更新ルール^[36]、ジャンピング ナレッジ^[37]などの対策により、オーバースムージングを軽減できます。最終層を完全に隣接する層に変更する、つまりグラフを完全グラフとして考えることで、長距離依存性が必要な問題におけるオーバースクワッシングを軽減することができます。^[34]${\displaystyle n}$${\displaystyle n}$

^{MPNNの他の「フレーバー」は、グラフ畳み込みネットワーク[7]}やグラフアテンションネットワーク[9]など^{[6 ]}の文献で開発されており、その定義はMPNN形式で表現できます。

グラフ畳み込みネットワーク（GCN）は、2017年にトーマス・キプフとマックス・ウェリングによって初めて導入されました^。[7]

GCN レイヤーは、グラフ上の局所スペクトルフィルターの1 次近似を定義します。GCN は、畳み込みニューラル ネットワークをグラフ構造データに 一般化したものと考えることができます。

GCN レイヤーの正式な表現は次のとおりです。

${\displaystyle \mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)}$

ここで、はノード表現の行列、はノード特徴の行列、は活性化関数（例：ReLU）、は自己ループが追加されたグラフ隣接行列、は自己ループが追加されたグラフ次数行列、は訓練可能なパラメータの行列です。 ${\displaystyle \mathbf {H} }$${\displaystyle \mathbf {h} _{u}}$${\displaystyle \mathbf {X} }$${\displaystyle \mathbf {x} _{u}}$${\displaystyle \sigma (\cdot )}$${\displaystyle {\tilde {\mathbf {A} }}}$${\displaystyle {\tilde {\mathbf {D} }}}$${\displaystyle \mathbf {\Theta } }$

特に、 をグラフ隣接行列とすると、 および を定義できます。ここで、は単位行列を表します。この正規化により、の固有値がの範囲内に制限され、数値的不安定性と勾配の爆発/消失が回避されます。 ${\displaystyle \mathbf {A} }$${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I} }$${\displaystyle {\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}}$${\displaystyle \mathbf {I} }$${\displaystyle {\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}}$${\displaystyle [0,1]}$

GCNの制限は、多次元のエッジ機能を許可しないことです。^[7]しかし、を課すことによって、つまり、隣接行列の各非ゼロエントリを対応するエッジの重みに等しく設定することによって、各エッジにスカラー重みを関連付けることは可能です。 ${\displaystyle \mathbf {e} _{uv}}$${\displaystyle w_{uv}}$${\displaystyle A_{uv}=w_{uv}}$

グラフアテンションネットワーク（GAT）は、2018年にPetar Veličkovićらによって導入されました。^[9]

グラフ アテンション ネットワークは、グラフ ニューラル ネットワークとアテンション レイヤーを組み合わせたものです。グラフィカル ニューラル ネットワークにアテンション レイヤーを実装すると、データ全体に焦点を当てるのではなく、データ内の重要な情報に注意を向けたり、フォーカスしたりできるようになります。

マルチヘッド GAT レイヤーは次のように表現できます。

${\displaystyle \mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

ここで、は注意ヘッドの数、はベクトル連結、は活性化関数（例：ReLU）、は注意係数、は- 番目の注意ヘッドのトレーニング可能なパラメータの行列です。 ${\displaystyle K}$${\displaystyle {\Big \Vert }}$${\displaystyle \sigma (\cdot )}$${\displaystyle \alpha _{ij}}$${\displaystyle W^{k}}$${\displaystyle k}$

最終の GAT 層では、活性化関数を適用する前に各注意ヘッドからの出力が平均化されます。正式には、最終の GAT 層は次のように記述できます。

${\displaystyle \mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

機械学習における注意は、認知的注意を模倣する技術です。グラフ学習の文脈では、注意係数はノード間の重要度を測定します。 ${\displaystyle \alpha _{uv}}$${\displaystyle u\in V}$${\displaystyle v\in V}$

正規化された注目係数は次のように計算されます。

${\displaystyle \alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{z}\Vert \mathbf {e} _{uz}]\right))}}}$

ここで、は学習可能な重みのベクトル、は転置、はエッジ特徴（存在する場合）、は修正されたReLU活性化関数です。注意係数は、異なるノード間で簡単に比較できるように正規化されています。^[9]${\displaystyle \mathbf {a} }$${\displaystyle \cdot ^{T}}$${\displaystyle \mathbf {e} _{uv}}$${\displaystyle {\text{LeakyReLU}}}$

GCN は、注意係数が学習可能ではなく、固定されており、エッジの重みに等しい GAT の特殊なケースとして考えることができます。 ${\displaystyle w_{uv}}$

ゲート付きグラフシーケンスニューラルネットワーク（GGS-NN）は、2015年にYujia Liらによって導入されました。^[36] GGS-NNは、ScarselliらによるGNN定式化^{[2]を出力シーケンスに拡張したものです。メッセージパッシングフレームワークは、}ゲート付きリカレントユニット（GRU）セルへの更新ルールとして実装されています。

GGS-NN は次のように表現できます。

${\displaystyle \mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0} }$

${\displaystyle \mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}}$

${\displaystyle \mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})}$

ここで、はベクトル連結、はゼロのベクトル、は学習可能なパラメータの行列、は GRU セル、はシーケンス インデックスを表します。GGS-NN では、ノード表現は GRU セルの隠し状態と見なされます。初期ノード機能は、 GRU セルの隠し状態次元までゼロで埋められます。同じ GRU セルが各ノードの表現の更新に使用されます。 ${\displaystyle \Vert }$${\displaystyle \mathbf {0} }$${\displaystyle \mathbf {\Theta } }$${\displaystyle {\text{GRU}}}$${\displaystyle l}$${\displaystyle \mathbf {x} _{u}^{(0)}}$

ローカルプーリング層は、ダウンサンプリングによってグラフを粗くします。ここでは、提案されているいくつかの学習可能なローカルプーリング戦略を紹介します。^[28]それぞれの場合、入力はノード特徴の行列で表される初期グラフと、グラフ隣接行列です。出力は、ノード特徴の新しい行列と、新しいグラフ隣接行列です。 ${\displaystyle \mathbf {X} }$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {X} '}$${\displaystyle \mathbf {A} '}$

まず最初に

${\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}$

ここで、は学習可能な投影ベクトルです。投影ベクトルは、各グラフ ノードのスカラー投影値を計算します。 ${\displaystyle \mathbf {p} }$${\displaystyle \mathbf {p} }$

トップkプーリング層^[26]は以下のように形式化できる。

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

ここで、は上位k個の最高投影スコアを持つノードのサブセット、は要素ごとの行列乗算、はシグモイド関数です。言い換えれば、上位k個の最高投影スコアを持つノードは新しい隣接行列に保持されます。この操作により、投影ベクトルはバックプロパゲーションによって学習可能になります。そうでなければ、離散出力が生成されます。^[26]${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$${\displaystyle \odot }$${\displaystyle {\text{sigmoid}}(\cdot )}$${\displaystyle \mathbf {A} '}$${\displaystyle {\text{sigmoid}}(\cdot )}$${\displaystyle \mathbf {p} }$

まず最初に

${\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}$

ここで、は汎用順列等変 GNN レイヤー (例: GCN、GAT、MPNN) です。 ${\displaystyle {\text{GNN}}}$

自己注意プーリング層^[27]は以下のように形式化できる。

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

ここで、は上位k個の最高の投影スコアを持つノードのサブセットであり、要素ごとの行列乗算を表します。 ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$${\displaystyle \odot }$

自己注意プーリング層は、トップ k プーリング層の拡張として考えることができます。トップ k プーリングとは異なり、自己注意プーリングで計算される自己注意スコアは、グラフの特徴とグラフ トポロジの両方を考慮します。

グラフニューラルネットワークは、生物学におけるタンパク質折り畳み問題を解決するためにGoogleのDeepMindが開発した人工知能プログラムであるAlphaFoldの主要な構成要素の1つです。AlphaFoldはいくつかのCASPコンテストで1位を獲得しました。^{[38] [39] [37]}

ソーシャルネットワークは、ソーシャルグラフとして自然に表現されるため、GNNの主要な応用分野です。GNNは、社会的関係とアイテム関係の両方に基づいたレコメンデーションシステムの開発に使用されます。 ^{[40] [13]}

GNNは、いくつかの組み合わせ最適化アルゴリズムの基本的な構成要素として使用されています。^[41]例としては、与えられたグラフの最短経路やオイラー回路を計算すること、 ^[36]人間の手によるソリューションよりも優れている、または競争力のあるチップ配置を導き出すこと、 ^[42]分岐限定法における専門家が設計した分岐ルールを改善することなどが挙げられます。^[43]

グラフとして見ると、コンピュータネットワークはGNNで異常検出のために分析することができます。出所グラフ内の異常は、ネットワーク内の悪意のある活動と相関していることがよくあります。GNNは、個々のノード^[44]やパス^[45]内でこれらの異常を識別して悪意のあるプロセスを検出したり、エッジレベル^[46]で横方向の移動を検出したりするために使用されています。

給水システムはグラフとしてモデル化することができ、GNNの直接的な応用である。この種のアルゴリズムは水需要予測に適用されており、^[47]地区測定エリアを相互接続することで予測能力を向上させている。このアルゴリズムの給水モデル化における他の応用としては、メタモデルの開発がある。^[48]

• https://distill.pub/2021/gnn-intro/