サーベイ論文の確認と追加調査⑤(Recurrent graph neural networks)｜Graph Neural Networkの研究を俯瞰する #5
グラフ理論やCNNをグラフ理論に応用したグラフ畳み込みネットワークについては下記で以前に簡単に取り扱いました。
ベースライン論文におけるGraphのCNN学習アルゴリズム｜ベースから理解するGraph Convolutional Networks #2 - Liberal Art’s diary
もう少し俯瞰的に取り扱えればということで簡単に調べてみたのですが、2019年のサーベイ論文を見つけましたのでこちらを読み進めつつ必要に応じて追加調査を行えればと思います。
[1901.00596] A Comprehensive Survey on Graph Neural Networks
#1ではAbstractについて、#2ではIntroductionについて、#3ではBackground & Definition(Section2)について、#4ではCategorization and Frameworks(Section3)について取り扱いました。
サーベイ論文の確認と追加調査②(Introduction)｜Graph Neural Networkの研究を俯瞰する #2 - Liberal Art’s diary
サーベイ論文の確認と追加調査④(Categorization and Frameworks)｜Graph Neural Networkの研究を俯瞰する #4 - Liberal Art’s diary
#5ではSection4のRecurrent graph neural networksについて取り扱っていきます。
以下目次になります。
1. Recurrent graph neural networks
2. まとめ
1. Recurrent graph neural networks
1節ではSection4のRecurrent graph neural networksについて取り扱います。
第一パラグラフでは、RecGNNs(Recurrent graph neural networks)がGNNsの初期のエポックメイキングな研究であるということに触れた上で、初期の研究ではマシンのリソースの制約で有向非巡回グラフ(DAG; Directed Acyclic Graphs)にフォーカスしていたことについて言及されています。
有向非巡回グラフは、上記のように閉路を持たない有向グラフで、ある頂点から出発した時に
に戻ってこないグラフであるとされています。
また、上記はWikipediaの記事の図をお借りしましたが、全てのノードが一度他のノードに推移すると自身に戻ってくることがないことが確認できます。また、全ての矢印は最終的に2と10のノードにたどり着くようになっていることも確認できます。このような性質を使うことで有効非巡回グラフは時間ステップに関連するモデリングに使うことができます。
第二パラグラフでは、Scarselliなどによって提案されたGNN*(Graph Neural Network)は、先行研究におけるrecurrentなモデルが有向非巡回グラフ(DAG)前提だったのに対し、無向グラフや巡回型のグラフにも適用できるようになったとされています。その他のGraph Neural Networksの研究と区別するために、ここではGNN*と表記しているようです。GNN*では安定的な均衡状態に到達するまで、ノードが再帰的に近傍のノードと情報交換し、自身の状態をアップデートすることについて記載されています。また、この処理の流れを数式(1)で表現されています。エッジやノードの属性と、ステップt-1におけるを用いることで次ステップのtにおける
を計算しています。
第三パラグラフでは、GRU(Gated Recurrent Unit)を導入したGGNN(Gated Graph Neural Network)について記載されています。
GRUは上記のようなUnitでLSTMに似ています。こちらを用いることで数式(2)のようにの計算を行なっています。GNN*などと違い、GGNNはBPTT(back-propagation through time)アルゴリズムを用いてモデルのパラメータを学習させるとされています。とはいえ、このGGNNは大きなグラフに適用するにはメモリ保持を必要とするという問題点があると言及されています。
第四パラグラフでは、大きなグラフを取り扱う上でのGGNNの課題を解決するにあたって提案された、SSE(Steady-state Embedding)が紹介されています。SSEではノードの隠れ層のアップデートを確率的かつ非同期な流れで、パラメータのアップデートを行うとされています。安定性も考慮し、数式(3)のようにハイパーパラメータのを用いて一部情報の保持ができるようにアップデートを行なっています。
2. まとめ
#5ではSection4のRecurrent graph neural networksについて取り扱いました。
#6では引き続き、Section5のConvolutional graph neural networksについて確認していきます。
