ベースライン論文の概要と事前知識の整理｜ベースから理解するGraph Convolutional Networks #1

上記の記事でグラフ理論についてまとめましたが、最近DeepLearningの文脈でもGraph Convolutional Networksが話題なので当シリーズはGraph Convolutional Networksについて取り扱っていきます。
#1では導入ということで、下記のベースライン論文の俯瞰とそれを踏まえて事前知識の整理を行えればと思います。

[1605.05273] Learning Convolutional Neural Networks for Graphs
以下目次になります。

1. ベースライン論文の概要
2. 事前知識の整理
3. まとめ

1. ベースライン論文の概要
1節では下記のベースライン論文のAbstractの和訳と補足を行います。シンプルにまとまっており非常に読みやすい内容です。

[1605.05273] Learning Convolutional Neural Networks for Graphs

Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs.

和訳：『多くの重要な問題はグラフデータの形で表現することができる。我々はCNNを用いて任意のグラフを学習するフレームワークについて提案する』

グラフ理論と可視化｜直感と数学 #3 - lib-arts’s diary
上記の記事でも紹介しましたが、グラフ表現を用いて様々な問題を描き表すことが可能です。たとえば単純な四則演算からNeural Network、DeepLearningなどの複雑な演算についてはグラフ表現で表すことができます（参照記事でTensorBoardについて言及しているので、そちらも参考にしてください）。このようにグラフの表現は記述力が高く非常に便利です。

These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes.

和訳：『任意のグラフは有向グラフ/無向グラフ、離散/連続のノードやエッジの属性を持つこともありうる。』
ここでは様々なグラフのパターンについて示唆しています。有向グラフ/無向グラフについては冒頭でご紹介した以前の記事にまとめましたのでそちらをご確認ください。後半の属性に関してですが、ノードやエッジはそれぞれ属性という値を持ちます。少々抽象的でわかりづらいので具体的な例を出すと、駅の路線図を考えた際に東京駅の持つ設備に関する情報などはノードの属性、東京駅と新宿駅をつなぐ路線として中央線や山手線があるのがエッジの属性の例と捉えておくと良いです。属性(attribute,property)は論文の後ろの方でinput channelsとして表記され、この辺知っておくと混乱しないで済むのでこちらは意識しておくと良いかと思います。

Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs.

和訳：『入力情報における局所的な位置情報を演算に組み込む画像ベースのCNNと同様に、グラフから局所的な位置情報を抽出する汎用的なアプローチを提案する。』
画像における畳み込みは3×3や5×5の近傍の値にフィルタを通して足し合わせるという処理を行います。このことにより位置に関する情報を取り込んで計算を行っていくことが可能になります。同様の処理をグラフの演算に組み込むにあたってどうしたら良いかということで、論文において手法が提案されています。

Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.

和訳：『以前よりあるベンチマークのデータセットを用いることで、我々は学習された特徴表現はSOTAのグラフカーネルと同等の成果を出し計算の効率性が高いことを示す。』
提案手法の性能に関するデモンストレーションについて言及されています。

2. 事前知識の整理
事前知識の整理としては論文の3のBackgroundで言及されているのでそちらについてまとめます。
まず3.1節では下記のようにCNNについてまとめられています。

CNNについては他の論文でも多く引用されているので特に気にしなくても良さそうです。引用が近年のDeepLearningのトレンドでのAlexNetやResNetなどではなく、LeCunなどの内容が中心なので、ベーシックなCNNに関しての引用となっています。
次に3.2節ではGraphs（グラフ）に関して言及されています。

基本事項に関しては上記のようにまとめられています。グラフはノードとエッジのペアであるで表され、とEはVを二次元に取ることで表現できます。同様な考え方に隣接行列がありますが、詳細は下記の記事でまとめているので省略します。ちなみにここでノードをVで表しているのはVertice(頂点)の略を意味しています。また、をとの距離を表すとしており、をノードの隣接ノード(1-neighborhood)としています。
上記までがグラフ理論の基本的な考え方で、次に論文で参考にしているPATCHY-SANが使用しているgraph labelingについてまとめます。graph labelingはl:V->S（S:ノードの次数など、何らかの方法でノードに順位づけを行ったもの）を元にVの変換を行います。この変換を元に論文ではグラフの畳み込みにあたっての変換を行っていきます。

3. まとめ
#1ではGraph Convolutional Networksのベースライン論文のAbstractとSection3のBackgroundについて取り扱うことで、概要の理解と事前知識の整理を行いました。
#2ではSection4で言及されている具体的なアルゴリズムについてまとめていければと思います。