ベースライン論文におけるGraphのCNN学習アルゴリズム｜ベースから理解するGraph Convolutional Networks #2

f:id:lib-arts:20190511123120p:plain

最近DeepLearningの文脈でもGraph Convolutional Networksが話題なので当シリーズはGraph Convolutional Networksについて取り扱っていきます。

[1605.05273] Learning Convolutional Neural Networks for Graphs
#1では導入ということで、上記のベースライン論文の概要とそれを踏まえて事前知識の整理を行いました。
https://lib-arts.hatenablog.com/entry/graph_cnn1
#2ではベースライン論文に記載のArbitrary Graphsに対してのCNNの学習アルゴリズムについてまとめていきます。
以下目次になります。

1. 学習アルゴリズムの全体に関して(Section4 冒頭)
2. 学習アルゴリズムの各STEPに関して
2-1. Node Sequence Selection(Section 4.1)
2-2. Neighborhood Assembly(Section 4.2)
2-3. Graph Normalization(Section 4.3)
2-4. Convolutional Architecture(Section 4.4)
3. まとめ

1. 学習アルゴリズムの全体に関して(Section4 冒頭)
1節ではSection4の冒頭部についてまとめていきます。1stパラグラフでは通常のCNNの画像に対する適用についてまとめられています。こちらについては一般論なのであまり気にしなくて良さそうです。2ndパラグラフではCNNと#1でも軽く触れたPATCHY-SANを組み合わせるにあたって論述がされています。ここも前置きなので詳細は読み飛ばしで良さそうです。3rdパラグラフではグラフの集合が与えられた際のPATCHY-SANの処理ステップについてまとめられています。それぞれ「(1)グラフからノードの固定長系列を選択する」、「(2)選択された各々のノードの固定長の近傍を集める」、「(3)抽出されたグラフを正規化する」、「(4)得られた系列のパッチからCNNを用いて近傍に関する表現(representation)を学習する」の4ステップであるとされています。
上記の4つのステップはそれぞれSection4.1~4.4で章立てされているので、当稿では2-1~2-4でそれぞれについて補足を交えながらまとめていければと思います。

2. 学習アルゴリズムの各STEPに関して
2-1. Node Sequence Selection(Section 4.1)
論文の4.1では"Node Sequence Selection"（ノード系列の選択）について説明されています。具体的には受容野(receptive field)を求めるノードを明確にするプロセスとされています。

f:id:lib-arts:20190512141049p:plain
上記は論文で書かれているAlgorithm1ですが、具体的には $V_{sort}$ の計算と $w$ 回繰り返し文を実行することで何らかの基準に沿って順序づけられたノード群から上から $w$ 個のノードを抽出する形になっています。
この際に重要になるのがノードを順序づけるアルゴリズムで、この際に用いられるのが論文のSection3や#1で言及したgraph labelingです。具体的にはノードの次数(degree)を計算したりあるノードからの距離を計算するなどでgraph labeling（数式上では写像 $l$ という風に表現されています）によってノードの順位づけは行うことができます。

2-2. Neighborhood Assembly(Section 4.2)
次に論文の4.2ではノードの近傍を集めるという処理について説明されています。

f:id:lib-arts:20190512141751p:plain
具体的には2-1節で示したAlgorithm1の6行目のRECEPTIVEFIELDの計算の中で、上記のAlgorithm3を呼び出していますがその中のNEIGHASSEMBの関数が行う処理に関してSection4.2では言及されています。

f:id:lib-arts:20190512141840p:plain
NEIGHASSEMBは上記のAlgorithm2でまとめられており、Section4.2の内容はこちらを説明しています（AlgorithmとSectionの切り分けが結構紛らわしいので読み解くにあたっては注意が必要です）。
処理としてはノードの $v$ と受容野のサイズ(the size of receptive field)の $k$ が与えられた際に幅優先探索(breadth-first search)を行いノードを集め、それを受容野の候補とするという処理になっています。
この際に候補ノードの数がkになるまでもしくは候補に追加できるノードがなくなるまで繰り返しで探索を行います。

2-3. Graph Normalization(Section 4.3)
論文の4.3では4.2で得られたノードの近傍ノード群をグラフ空間からベクトル空間に変換することについて説明されています。

f:id:lib-arts:20190512143941p:plain
具体的な問題を元に解説されているのですが文章が長くて読むのが大変なので、上記のFigure3をベースに掴むのが良いかと思われます。4.1で選んだノードに対して4.2で近傍のノードを集め、4.3で行列形式で扱えるようにしているという認識で良いかと思います。

2-4. Convolutional Architecture(Section 4.4)
論文の4.4では畳み込みに関して説明されています。まず $a_{v}$ と $a_{e}$ が二つ出てきます。こちらは#1でも言及しましたがノード(V: Vertex)とエッジ(E: Edge)のそれぞれの属性の数を表しています。教科書で勉強しただけだとノードとエッジの値がそれぞれ一つだという誤解を生みがちなので、この辺は注意が必要です。この $a_{v}$ と $a_{e}$ を踏まえた上で入力されたグラフのGに対してノードとエッジに関する受容野(receptive field)を構築します。畳み込みのtensor(スカラー、ベクトル、行列を含んだ多次元配列)表現としては、ノードが $( w,k,a_{v} )$ 、エッジが $( w,k,k,a_{e} )$ です。またこれはそれぞれ $( wk,a_{v} )$ と $(wk^2,a_{e})$ に変形(reshape)できるとも言及されています。
ここで $a_{v}$ と $a_{e}$ はそれぞれInput Channels(cf. 画像認識におけるRGBが3チャネル)にあたるとされています。