Overview｜Graph Neural Networkの理解を試みる #1

以前の記事でGraph Neural NetworkのSurveyやその他論文などについて確認しました。

[1901.00596] A Comprehensive Survey on Graph Neural Networks

上記のSurveyなどはわかりやすかったので、10回のシリーズとして確認し、その内容をテキストで取りまとめも行いました。

上記で参照したのはわかりやすいSurveyでしたが、テキストをSurveyの記載に準拠させ過ぎたことで解説としてわかりにくいのではという印象もあります。そのためこの度改訂を行うことにしました。

改訂を行うにあたって、以前の内容と統合しつつ再編が少々大変だと思われたため、先にいくつかの記事でドラフトの記載を行い、その内容を再編する形式で進めようと思います。#1では以前確認したSurveyとは別のSurveyである、"Graph Neural Networks: A Review of Methods and Applications"の内容を簡単に確認し、Graph Neural Networkの理解に関連する内容についてまとめます。

[1812.08434] Graph Neural Networks: A Review of Methods and Applications

以下、当記事の目次になります。
1. Surveyの確認
2. MPNN(Message Passing Neural Network)について
3. NLNN(Non-Local Neural Network)について
4. GN(Graph Network)について
5. まとめ

1. Surveyの確認
GNNの理解に関連する"Graph Neural Networks: A Review of Methods and Applications"の記載は主にSection2に記載されているので、Section2を主に確認します。

まず上記がSurveyのSection2の冒頭ですが、Section2-1ではオリジナルの文脈のGNN(The graph neural network model,2009)について、Section2-2ではGNNの派生について、Section2-3では3つの一般的なフレームワーク(three general framework)について、それぞれ取り扱っていると記載されています。当記事では「理解」を主目的とするため、以下1節ではSurveyのSection2-3を確認することとします。

Section2-3の冒頭の記載では、3つの一般的なフレームワークとして、MPNN(Message Passing Neural Network)、NLNN(Non-Local Neural Network)、GN(Graph Network)の3つが紹介されています。ざっくりと理解するなら、MPNNはGraph Convolutional Networkや他の様々なGNNを統合したもの、NLNNはTransformerのようなself-attentionの手法を統合したもの、GN(Graph Network)はMPNNとNLNNを統合したものと把握しておけば良いかと思います。ここで[66]で表された論文がTransformer(Attention is All you Need)の論文であることも抑えておくと良いかと思います。

当記事では以下、2節でMPNNに関してSurveyのSection2-3-1の記載について、3節でNLNNに関してSurveyのSection2-3-2の記載について、3節でGNに関してSurveyのSection2-3-2の記載についてそれぞれ確認できればと思います。

2. MPNN(Message Passing Neural Network)について
2節ではMPNN(Message Passing Neural Network)について確認します。

上記はSurveyのSection2-3-1の記載ですが、式34のメッセージ伝播フェーズ(message passing phase)と、式35の読み出しフェーズ(readout phase)の二つのフェーズでニューラルネットワークが構成されると記載されています。このように表せるMPNN(Message Passing Neural Network)のフレームワークで、様々の設定に基づくGraph Neural Networkが表せるとされています。

上記ではMPNNによる表記の統合の具体的な例として、GGNN(Gated graph sequence neural networks, 2016)の表記が取り扱われています。式36ではを、をで表すなどで、処理の内容を具体化していると把握すれば良いです。

このようにMPNNのframeworkを用いることで様々なGNNについて表記できると抑えておくと良いかと思います。

3. NLNN(Non-Local Neural Network)について
3節ではNLNN(Non-Local Neural Network)について、SurveyのSection2-3-2の記載を確認します。

上記では式37が汎用的な非局所演算(generic non-local operation)の定義とされています。は出力の位置で、が任意の位置を表すとされており、がとの関係性を表すスカラー値、が入力のの変換、が結果の正規化に用いられる項と記載されています。

NLNNのイメージはTransformerと同様に考えておくとよく、Section2-3-2ではTransformerで用いられるDot productについても紹介されています。

4. GN(Graph Network)について
4節ではGN(Graph Network)について、SurveyのSection2-3-3の記載を確認します。

上記が冒頭部の記載ですが、Surveyでは"Relational inductive biases, deep learning, and graph networks"よりgraph definition、GN block、computational steps、basic design principlesなどについて紹介を行なうとされています。

[1806.01261] Relational inductive biases, deep learning, and graph networks

graph definitionではグラフの数式的な定義についてまとめられています。の3-tupleでグラフを表し、は大域的な特徴量(global attribute)、はノードの特徴量(node's attribute)、はエッジの特徴量、とはを考えるにあたってのノードのインデックス(エッジなのでノードは2つ必要)を表すとされています。また、がsender、がrecieverを表すとされています。

GN block、computational stepsについては上記のようにそれぞれ記載されています。

Design Principlesについては上記のように記載されており、flexible representations、configurable within-block structure、composable multi-block architecturesの3つが紹介されています。

5. まとめ
#1では"Graph Neural Networks: A Review of Methods and Applications"の内容を元に、Graph Neural Networkの汎用的な構造に関して、MPNN(Message Passing Neural Network)、NLNN(Non-Local Neural Network)、GN(Graph Network)についてそれぞれ取り扱いました。
4節の記載は流したので、#2ではGraph Networkの元論文について確認を行えればと思います。