論文紹介: Stochastic Training of Graph Convolutional Networks with Variance Reduction



# tl;dr

* Graph convolutional networks (GCN)において、理論的・実験的によく収束するミニバッチ学習法を提案
* サンプリングを行い、サンプリングされなかった近傍ノードについては、以前計算した隠れ層の値を保持しておき、その値を使うことで分類器のvarianceを下げる
     - この考え方をControl variateと呼ぶ
* 実験的に、既存手法より少ないエポック数・時間で収束することを確認。


```
@InProceedings{pmlr-v80-chen18p,
  title = 	 {Stochastic Training of Graph Convolutional Networks with Variance Reduction},
  author = 	 {Chen, Jianfei and Zhu, Jun and Song, Le},
  booktitle = 	 {Proceedings of the 35th International Conference on Machine Learning},
  pages = 	 {942--950},
  year = 	 {2018},
  editor = 	 {Dy, Jennifer and Krause, Andreas},
  volume = 	 {80},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Stockholmsmässan, Stockholm Sweden},
  month = 	 {10--15 Jul},
  publisher = 	 {PMLR},
  url = 	 {http://proceedings.mlr.press/v80/chen18p.html}
}
```

# 目的

Graph convolutionとは、グラフデータを直接ニューラルネットワークで畳み込む手法の総称です。自然界では非常に多くの事象がグラフ構造として現れるため、それを直接扱えるGraph convolutionが注目されています。例えば、分子構造やSNSの"つながり"はそれぞれグラフ構造です。また、画像も上下左右に接続があるグラフとして表現できます。

Graph convolutionには様々なアプローチがあります（詳しくは[piqcyさんの素晴らしい資料を参照](https://medium.com/programming-soda/graph-convolution%E3%82%92%E8%87%AA%E7%84%B6%E8%A8%80%E8%AA%9E%E5%87%A6%E7%90%86%E3%81%AB%E5%BF%9C%E7%94%A8%E3%81%99%E3%82%8B-part1-b792d53c4c18)）が、近年よく使われるアプローチとしてKipfらによる[Graph convolutional networks (GCNs)](https://openreview.net/pdf?id=SJU4ayYgl)が知られています。GCNは非常に明快なアプローチで、各層ごとに近傍1ノード（とそのノード自体）の情報を畳み込みます。層を重ねるごとに遠くのノードまで参照するようになります。

![GCN.png](https://qiita-image-store.s3.amazonaws.com/0/152362/012365dd-a936-23bb-915d-2cee2ca60555.png)


([Kipf. 2018. Structured deep models: Deep learning on graphs and beyond. Presentation.](http://tkipf.github.io/misc/SlidesCambridge.pdf))

GCNはGCN以前のアルゴリズムよりも高速で、実験的にも良い性能を示すことがわかっています。GCNを礎としたGraph convolutionの手法が近年いくつも提案されています。

さて、そんなGCN(とその派生物)ですが、近年の深層学習とは異なり**バッチ学習を行う必要があるという欠点**があります。バッチ学習とは、データを小さなミニバッチにわけ確率的勾配法を行うミニバッチ学習に対して、データ全体を用い勾配法で学習する手法です。バッチ学習にはデータを全てGPUにのせるのでデータサイズに対してスケールしないという問題があります[^1]。本研究では、GCNで、理論的・実験的によく収束するミニバッチ学習法を提案します。

[^1]: 収束性などについては本論文では議論しません。

# GCN

まず、GCNについてさらっと説明します。なお、本論文では無向グラフを前提にします[^2]。

[^2]: 有向グラフにしても同じ議論は成り立ちそうに見えるが、論文内では特に言及されていない。

GCNは前述したとおり近傍1ノード(とノード自体)の特徴量に重みを掛け、それを足し合わせることで次の層の特徴量を計算します。表記の簡単のため（と高速に行列計算を行うために）この操作を行列計算で書き表します。

![eq1.png](https://qiita-image-store.s3.amazonaws.com/0/152362/fe4dd3fe-fb21-6faf-6f3d-44ee2482cb31.png)



$X$は$V$個のノード×$M$次元の特徴量の2次元配列であり、各ノードの特徴量を示します。これに対して重み$W$が右側から掛けられており、これはニューラルネットワークで普通に見られる線形変換です。$P$はAdjacency matrixを正規化したものです。Adjacency matrixとは$V \times V$の大きさの行列で、$(i, j)$要素は、$i$番目のノードと$j$番目のノードの接続の重みを示しています。これを左側から掛けることで、出力の$i$行目には、Adjancency matrixの$i$行目で非零のノードの特徴量が足し合わされた結果が格納されます。


![AdjacencyMatrix_1002.gif](https://qiita-image-store.s3.amazonaws.com/0/152362/56daecb8-da7c-42e5-597e-6891b9a262dd.gif)


(From http://mathworld.wolfram.com/AdjacencyMatrix.html )


# 先行研究

GCNでミニバッチ学習を行うという試みはいくつか知られています。ナイーブな方法としては、各層で近傍ノードをサンプリングしてしまうことが考えられます。しかしながらこの方法は正しい近似を与えることができず、サンプルサイズを大きくしないといけないためスケーラビリティに問題があります。

他の手法として、近傍ノードのサンプリングをもう少し賢くやろう（重要なノードをサンプリングしよう）という方法があります。しかしながら、この方法でも学習が収束することは理論的に保証されません。しかも、著者らによると、この手法は普通のサンプリングよりも実験的に劣った結果となることが多いようです。

本研究では、これらの手法とは一線を画し、収束が理論的に保証される方法を提案します。

# 提案手法

## 提案手法の考え方

提案手法はシンプルです。普通のサンプリングと同じように近傍ノードからいくつかのノードをサンプリングします。このとき、サンプリング**されなかった**近傍ノードについては、**以前計算した隠れ層の値を保持しておき、その値を使います**。

![eq2.png](https://qiita-image-store.s3.amazonaws.com/0/152362/ee51d1db-991d-d465-8ce8-4216ae2897ed.png)

下側の式が提案手法の近似式ですが、$\hat{\mathbf{n}}$のハットがサンプリングしていることを示しています。$\bar{h}$が以前計算した隠れ層の値です。隠れ層の値$h_v^{(l)}$は、$h_v^{(l)} = {\bar{h_v}^{(l)}} + \Delta h_v^{(l)}$、つまり記録されていた$\bar{h}$と、計算しなおした時の差分$\Delta h_v^{(l)}$の和で表されます。したがって、この式は、前述した"サンプリングを行い、サンプリングされなかった近傍ノードについては、以前計算した隠れ層の値を保持しておき、その値を使う"ということを示しています。

ここで重要なのは、"以前の状態”という知識を使って、推測のばらつき(variance)を抑えるところです。このような方法をControl variateと呼びます（論文の題名を回収）。証明は割愛しますが、このような方法を使うことでサンプルサイズによらず、必ずどこかの局所解に落ち着くことが理論的に示せます。

## 具体的な方法

上記に提案手法の考え方を載せましたが、具体的な方法についても説明します。提案手法における一回の更新は次のように行われます。

1. まず出力層で適当な数のノードを選びます。
2. 選んだノードのうち所定の数Dの近傍ノードをサンプリングします。
3. 各層で、選んだノードとサンプリングしたノードに対して2を繰り返します。サンプリングしたノードに対してもさらにサンプリングするので、L層のネットワークでは最悪の場合$D^L$個のノードが選ばれることになります。
4. 各層について、選ばれたノードをもとにAdjacency matrixを計算します。イメージ的にはサンプリングされなかった接続$(i, j)$の値を0埋めすると思えば大丈夫です。
5. あとは前述した行列式を使ってForward propagationとbackward propagationを行います。この部分はTensorflowなどのフレームワークを使って普通に実行できます。
6. ここまでで対象となったノードについては、その隠れ層の値を記録します。

この手法では、モデルの重み$W$だけでなく、隠れ層の値$h$も保持しておくところがポイントです。

ちなみに、予測時に全ての$h$をバッチ法で再計算しても良いのですが、これでは結局メモリが多くかかってきてしまうことが問題です。そこで、予測時にはback propagationを行わず、適当にサンプリングしつつ$\bar{h}$の値を更新してゆくことで、求めたい$h$の値を完全に近似できることを著者らは証明しています。

## その他の工夫

著者らは上記のControl variateの仕組みを使い、GCNにdropoutを適用する方法を提案しています(内容は割愛)。

また、先行研究がDropoutを近傍ノードの集約前にやっているのに対して、提案手法は集約後にやっています。前者は各ノードに対してdropoutを行うので、後者よりも計算量が多く、著者らは実験的には性能は変わらないので高速な後者を選んだと説明しています。


# 実験

提案手法の性能を実験します。本実験では提案手法はミニバッチサイズを2として実験しています（この2の中にはノード自身と、その近傍1つが含まれる）。

![figure.png](https://qiita-image-store.s3.amazonaws.com/0/152362/8e4c38aa-d7f3-9135-2335-5a1326ae5f3d.png)

6つのデータセット上で実験を行いました。黒線のM1+PPがバッチ学習を行う通常のGCNの代替としてミニバッチサイズを大きくとった提案手法[^3]、緑線のCV (Control Variate) が提案手法です。NSは普通のサンプリング(近傍サンプリング; neighbor sampling)、ISは重要度に基づくサンプリング (importance sampling)です。ご覧のとおり、提案手法の緑線は黒線とほぼ重なっており、提案手法はバッチ学習と同等程度のスピードで収束しています。

[^3]: 本来のバッチ学習では時間がかかりすぎるため。バッチ学習した場合と同等の性能を実現できることを前の実験で確かめている。とはいえ、なぜこのような操作をしたのかちょっと苦しい。

この収束の速度をもう少し定量的に見てみます。

![figure.png](https://qiita-image-store.s3.amazonaws.com/0/152362/13eeecbd-e9eb-c0fb-9c89-7701535648a7.png)

これは、提案手法とベースラインが96%の精度を実現するまでにかかった時間を示しています。必要なエポック数ではしたM1+PPに相当するExactが少ないですが、提案手法は他のサンプリングアルゴリズムに比べると非常に少ないエポック数収束していることがわかります。また、提案手法はExactに比べると行列がスパースになっているので、実際の学習時間としてはExactよりもだいぶ短くなっています。

# コメント

* 本手法は、学習データ上の局所解にたどり着くことを保証しているが、それが大域最適なのかや、その汎化性については議論していないので注意。
    - GCNはまだまだ新しい技術なので今後そのあたりの理論が進むことを期待。CNNやMLPはGCNの特殊な場合なので、GCNを研究することはニューラルネットワーク全体を理解することに繋がる。
* 毎更新ごとに、保持した以前の状態をGPUメモリにのっける必要があるのでまだまだ非効率が多い。特に接続が多いグラフだとGPUメモリ的に辛くなりそうな気がする。