サーベイ論文の確認と追加調査③(Background & Definition)|Graph Neural Networkの研究を俯瞰する #3

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

グラフ理論や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について取り扱いました。

サーベイ論文の確認と追加調査①(Abstractで掴む概要)|Graph Neural Networkの研究を俯瞰する #1 - Liberal Art’s diary

サーベイ論文の確認と追加調査②(Introduction)|Graph Neural Networkの研究を俯瞰する #2 - Liberal Art’s diary

#3ではBackground & Definitionについて取り扱っていきます。
以下目次になります。
1. Background(Section2-A)
2. Definition(Section2-B)
3. まとめ


1. Background(Section2-A)
1節ではBackgroundを取り扱います。

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

まず冒頭部でSperdutiが1997年の研究でニューラルネットワークを有向非巡回グラフ(DAG; Directed Acyclic Graphs)に適用したことについて記載されています。この後のGori(2005)やGallicchio(2010)の初期の研究がRecGNNs(Recurrent Graph Neural Networks)にまとまっていったと言及されています。RecGNNsでは近隣のノードの情報(neighbor information)を伝播させることで対象のノードの表現(node's representation)を学習すると記載されています。

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

第二パラグラフでは、Computer Visionの分野で成功したCNNに触発されて開発されてきているアルゴリズムとして、ConvGNNsについて紹介されています。ConvGNNsは大きく分けると二つの主要な流れ(main streams)があり、それぞれspectral-basedとspatial-basedであるとされています。それぞれの詳細についてはSection3で取り扱っているとされていますが、研究の整理としてはTable2にまとめているとされています。

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

上記のTable2では、Graph Neural Networkの先行研究を整理してまとめられています。RecGNNs、ConvGNNs、GAEs、STGNNsの4分類に論文をそれぞれ分類しています。ちなみに26番の論文は以前ご紹介した"Learning convolutional neural networks for graphs"の論文になります。

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

こちらの論文はspatial-basedと把握しておくと良いと思います。

以降のパラグラフでは、"Graph neural networks vs. network embedding"としてGNNsとnetwork embeddingの比較や"Graph neural networks vs. graph kernel methods"としてGNNsとグラフカーネル法の比較について言及されています。


2. Definition(Section2-B)
2節ではSection2-BのDefinitionについて取り扱います。

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

冒頭部の記述では、論文を通しての記法の注意として太字の大文字は行列(matrices)を表し、太字の小文字はベクトルを表すとされています。それぞれの詳細についてはTable1にまとめたとされています。

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

Table1には上記のように様々な記法についてまとめられています。それぞれの説明につてはDefinition1〜Definition3に記載されているので、そちらを確認していきます。

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

Definition1ではグラフ(Graph)に関しての定義がまとめられています。グラフはG=(V,E)のように表し、Vはノードの集合(VはVerticeからとっています)、Eはエッジの集合を表すとされています。また、ノードをv_{i} \in V、エッジをe_{ij}=(v_{i},v_{j}) \in Eと表しています。次にノードの近傍(neighborhood)のノードをN(v)= \{u \in V|(v,u) \in E \}、隣接行列(adjacency matrix)をAと表すとされています。またノードの属性を\mathbf{X} \in \mathbf{R}^{n \times d}、エッジの属性を\mathbf{X}^{e} \in \mathbf{R}^{m \times c}と表すとなっています。ここで注意すべきは、ノードとエッジの属性は1つとは限らず複数ある場合もあるという点です。ここでは一つのノードあたりd個の属性、一つのエッジ(二つのノードのペアに対するエッジ)はc個の属性を持つと考えられます。また、この時nはノードの個数、mはエッジの個数であるとされています。

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

Definition2では有向グラフ(Directed Graph)についてまとめられています。無向グラフ(Undirected Graph)は有向グラフの特殊なケースで、隣接行列が対称(symmetric)であるとき無向グラフであるとされています。

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

Definition3ではノードの属性の\mathbf{X}が時間によって変動するグラフのことをSpatial-Temporal Graphであると定義しています。

上記で取り扱った内容はグラフを取り扱う上での定義になってくるので、しっかり押さえておきたいところです。

 

3. まとめ
#3ではSection2のBackgroundとDefinitionを確認しました。
#4では引き続き、Section3のCategorization and Frameworksについて取り扱っていきます。