Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networksを読んだのでメモ
はじめに
Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networksを読んだのでメモ.
気持ち
GNNの表現力の低さを問題視した論文.この問題は以前読んだICLR2019のHow Powerful are Graph Neural Networks?でも議論されている.GNNは(データとタスクによるが)一般的なNNに比べ学習データにoverfitすることすらできないことがある.そのためこの論文ではGNNの表現力を向上させるgraph warp module (GWM)を提案するというもの.GWMは既存のGNNに追加モジュールとして組み合わせることが可能.
GWMのポイントはグラフの持つグローバルな特性を捉えるためのvirtual supernodeの導入と,正確なノード間の情報のやりとりを達成するためのGRUとattention利用した構造の2点とのこと.
notation
グラフをとし,はそれぞれノードとエッジの集合を表す.ノードのラベルをとして,各エッジをノードのペアとして表現する.隣接行列は重み付きとし,各ノードには特徴ベクトルを割り振る.ここでは多層構造のGNNを,平滑化関数を利用して再帰的に出力を計算するものとして考える.初期値をとしをGNNの層目によって番目のノードに割り当てられた特徴ベクトルとする.最終的に得られた特徴ベクトルの集合を集約することで出力を得る.
Graph Warp Module
GWMはsuper node, transmitter unit, warp gate unitの3つのブロックから構成されていて,GWM付きのGNNは層目からのメッセージをsupernodeの値と合わせ混んでl層目の出力として返す.
Supernode
Supernodeは全てのノードと接続を持つノードで,GNNの各層に用意される.Supernodeは全てのノードと接続を持つため,グローバルな情報を伝達する助けとなるとのこと.層目のsupernodeの特徴ベクトルをとすると,各層においてtransmitterと呼ばれるunitはsupernodeから層目に渡すメッセージを要求し,メインのGNNにメッセージを送る.ただし,はsmooth function.
層目のsupernodeの特徴ベクトルは層目のsupernodeの特徴ベクトルを利用して作られるため,初期値は何らかの値で初期化されている必要がある.ここでは初期値の例としてノードやエッジの数,入力ノードの特徴量の平均やヒストグラムなどを挙げている.
Transmitter Unit
Transmitter unitはGNNとGWM間のメッセージのやり取りを扱うユニット.ここでは複数のタイプのメッセージを扱うために,attentionを利用する工夫を入れている.GNNからsupernodeにメッセージを送る前に,transmitterは-head attention mechanismを使ってメッセージをタイプごとに集約する.処理の流れとしては,GNNからsupernodeへと送るメッセージを作成,伝送.その後supernodeからのメッセージをGNNへ伝送の流れ.細かい計算は次のようになる.
の部分がattention.
Warp Gate
Warp geteは送られてきたメッセージをマージしてその結果をGRUを通してsupernodeとGNNに送るというもの.構成要素は以下.
・:層目のGNNにメッセージを伝送するGRUの入力 ・:層目のsupernodeにメッセージを伝送するGRUの入力 ・:層目のsupernodeからのメッセージ ・:層目のGNNからのメッセージ:supernodeからGNNへの伝送のためのwarp gate coefficients ・:GNNからsupernodeへの伝送のためのwarp gate coefficients
各変数の具体的な定義は以下.
これらをGRUに通してGNNとsupernodeのメッセージを組み合わせた値を返す.
まとめ
モチベーションははHow Powerful are Graph Neural Networks?と同じだがこの論文は問題の解決方法がpracticalで個人的にはHow Powerful are Graph Neural Networks?の方が好き.ただ,既存の枠組みに導入するだけで性能改善可能という点は扱いやすく,良い手法.