PyTorchで学ぶGraph Convolutional Networks

**[ツイッター](https://twitter.com/omiita_atiimo)で人工知能のことや他媒体で書いている記事など** を紹介していますので、人工知能のことをもっと知りたい方などは**気軽に[フォロー](https://twitter.com/omiita_atiimo)してください！**

# PyTorchで学ぶGraph Convolutional Networks
この記事では近年グラフ構造をうまくベクトル化(埋め込み)できるニューラルネットワークとして、急速に注目されているGCNとGCNを簡単に使用できるライブラリPyTorch Geometricについて説明する。応用分野は生物学から、渋滞予測、レコメンダーシステムまで幅広い。
本記事は[GCN生みの親のブログ記事](http://tkipf.github.io/graph-convolutional-networks/)と[PyTorch Geometricの公式チュートリアル](https://pytorch-geometric.readthedocs.io/en/latest/index.html)をかなり参考にしております。

**読んで少しでも何か学べたと思えたら 「いいね」 や 「コメント」 をもらえるとこれからの励みになります！よろしくお願いします！**

## 1. Graph Convolutional Networksとは？
### 1.1 そもそもグラフとは？
ノードとエッジで定義される。折れ線グラフやヒストグラムといった類のグラフではないことに注意。具体例では、Facebookの友達関係(人がノードで友人関係がエッジ)や酵素の構造(原子がノードで結合関係がエッジ)など。(ここでは重みなし無向グラフとします。)

![簡単なグラフ](https://imgur.com/64WkDhx.png)

それぞれがそれぞれの特性を持つ。
またグラフは数学的に行列で表すことができ、このGCNでは隣接行列と特徴行列の2つを用いる。

* 隣接行列: ノードとノードの結合関係を表す行列
* 特徴行列: 各ノードの特徴ベクトルを表す行列

先ほどの図の例を隣接行列と特徴行列で表すと以下になる。
オレンジ色の文字が各ノードを表す。例えば、隣接行列において1行目の3列目はノードaとノードcが接続されているため1が入っている。特徴行列は $x_1, x_2$ がそれぞれ特徴を示している。

![簡単なグラフの行列](https://imgur.com/75ANn9O.png)

### 1.2 GCNとは？
#### 1.2.1 概要
GCN(=Graph Neural Networks)とはグラフ構造をしっかりと加味しながら、各ノードを数値化(ベクトル化、埋め込み)するために作られたニューラルネットワーク。
GCNのゴールは **構造を加味して各ノードを数値化する** というところにある。

![GCNのゴール](https://imgur.com/LyU1GAa.png)


ここで、構造を加味しながらというのはつまり **いま注目しているノード(数値化したいノード)がどういったノードとくっついているかを加味しながら** 数値化していくと言える。
具体的にノードcについて考えると以下の図。

![注目ノードと隣接ノード](https://imgur.com/CqdpmNp.png)

同様に他のノードに対しても色付けを行うと以下の図。

![注目ノードと隣接ノードたち](https://imgur.com/djJ88DV.png)

これを全ノードに対して行う。
GCNは一言で言えば、**あるノードの隣接たちを見て埋め込むネットワーク** と言える。

GCNは2種類の行列を入力とし、1つの行列を出力する。

* 入力
  * 隣接行列 $\mathbf{A} \in \mathbb{R}^{n\times n}$ : どのノードとどのノードが繋がっているかを表す行列。
  * 特徴行列 $\mathbf{F}_{in} \in \mathbb{R}^{n\times |F|}$: 各ノードの特徴ベクトルを表す行列。
* 出力
  * 潜在行列 $\mathbf{H}_{out} \in \mathbb{R}^{n\times |H|}$: 各ノードの潜在表現ベクトルを表す行列。(GCNによる変換済)

#### 1.2.2 数式
早速だが、GCNを数式で表すと以下になる。

$$
\mathbf{H}^{(l+1)} = f(\mathbf{H}^{(l)}, \mathbf{A})
$$

ただし、$H^{(0)}=X$ である。

これでGCN自体の定義は終わりなのだが、ちょっと意味がわからないので具体例で見てみる。
ここで活性化関数をReLUとした1層のGCNを例にとってみる。先ほどのGCNの図を再掲する。ここで活性化関数はReLUが使われていると仮定している。

![GCNのゴール](https://imgur.com/LyU1GAa.png)

これを数式で表すと、

$$
f(H^{(0)}, A) = f(X, A) = \mathrm{ReLU}(AX\cdot W)
$$

となる。$W$ は通常のニューラルネットワークと同じく、重みである。 $A, X$ はそれぞれ隣接行列および特徴行列(入力)である。ここで **$AX$の意味について考えてみよう** 。
これは実際にAXを計算してみるとわかるのでやってみる。
再び以下のグラフを使う。

![簡単なグラフ](https://imgur.com/64WkDhx.png)

![簡単なグラフの行列](https://imgur.com/75ANn9O.png)

$AX$ を計算してみる。以下の図で隣接行列が1となっているところだけ色付けした。

![AXの計算結果](https://imgur.com/TlCRVS5.png)

たとえば、ノードcの計算結果を見てみると、隣接しているaとbの元々の特徴量を足し合わせた得られていることがわかる。
このことから、$AX$ つまり **隣接行列 $\times$ 特徴行列はあるノードと繋がっているノードたちの特徴量を足し算したもの**　であることがわかる。$AX$によって周りのノードたちを考慮した特徴量を獲得でき、あとはそれに通常のニューラルネットワークのように重み$W$を掛け算し、非線形の活性化関数 $\mathrm{ReLU}$ を適用しているだけである。

現時点である程度強いのだが、実は問題点が2つある。その2つを解決したものこそが一般的に使われているGCNである。それでは問題点とその解決方法を見ていこう。

#### 1.2.3 問題点と解決方法

1. **自身ノードの情報が入っていない**。(近傍ノードの情報のみ)
2. $AX$ の行列の乗算のせいで **各ノードごとにスケールが大きく異なってしまう**。

この2つの問題点を解決する方法はいたって簡単。
1. **隣接行列$A$に単位行列$I$を足して $\hat{A}=A+I$ とすることで自身ノードの情報も加える**。ここで$I$とは対角成分が1でそれ以外0の行列のこと。
2. **隣接行列 $\hat{A}$ を $\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$ として正規化**。つまり各行の合計値を1としている。ここで、$\hat{D}$ は $\hat{A}$ の次数行列。次数行列とは、対角成分が各ノードの次数でそれ以外0の行列のこと。

こうして最終的なGCNの式は以下の式となる。

$$
f(H^{(0)}, A) = \mathrm{ReLU}(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}X\cdot W)
$$

### 1.3 GCNの例
上の式で実現されたGCNを使って、複雑ネットワーク界隈のMNIST的存在である空手クラブネットワーク([Zachary (1977)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.336.9454&rep=rep1&type=pdf))の各ノードをベクトル空間に埋め込んでみる。まずは元々のネットワークは以下の図。ノードが空手クラブの部員、エッジが友人関係を示している。

![空手クラブネットワーク](https://imgur.com/6BSc8M3.png)

> Image Credit: [Kipf, T. et al. (2017)](https://arxiv.org/pdf/1609.02907.pdf)

同一色は同一クラスターを表しており、4つのクラスターがあることがわかる。これを3層GCNを使って各ノードを二次元空間に埋め込んだ結果が以下。**同じクラスター同士は近く、異なるクラスター同士は遠くに埋め込まれており、うまくいっている** ことがわかる。

![空手クラブネットワークのベクトル空間への埋め込み](https://imgur.com/x7OP7Q3.png)


> Image Credit: [Kipf, T. et al. (2017)](https://arxiv.org/pdf/1609.02907.pdf)


### 1.4 なぜGCNがうまくいくのか。
ここは主題であるPyTorch Geometricから離れてしまうので、詳しくは[参考文献](https://arxiv.org/pdf/1609.02907.pdf)を当たって欲しいが簡単にだけ説明すると、**GCNは、Weisfeiler-Lehmanアルゴリズムに①パラメータを持たせ、②微分可能性を追加した特殊ケースと捉えることができるため** うまくいっていると考えられる。

***(Weisfeiler-Lehmanアルゴリズムではノードの潜在表現は $\mathrm{hash}(AX)$ という任意のハッシュ関数を用いて獲得するが、GCNでは $\mathrm{ReLU}(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}X\cdot W)$ というパラメトリックでかつ微分可能な関数を用いていると考えられる。)***

## 2. GCNを使ってみよう
PyTorch Geometric(PyG)で実際にGCNに触れてみる。[PyGのチュートリアル](https://pytorch-geometric.readthedocs.io/en/latest/index.html)を順にやっていく。
ノートブックを日本語のコメント豊富に[こちらのGithub](https://github.com/omiita/PyTorchGeometric-Tutorial)にあげましたのでお手元で実行しながらお読みいただければ、より理解が深まるかと思います。

ここでは **インストール** と実際に **GCNレイヤーを使う** ところのみ紹介。より詳しいデータの準備などはGithub先の[ノートブック](https://github.com/omiita/PyTorchGeometric-Tutorial/blob/master/PyTorch_Geometric_Tutorial.ipynb)を参照してください。

### 2.1 PyGのインストール
pytorchのバージョンが1.2.0以上であることを確かめてください。pytorchが入っていなければ

```shell
$ pip install torch
```
でインストールしましょう。

```shell
$ python -c "import torch; print(torch.__version__)"
>>> 1.2.0
```

続いてPyTorch Geometricをインストールしてみましょう。

```shell
$ pip install --verbose --no-cache-dir torch-scatter
$ pip install --verbose --no-cache-dir torch-sparse
$ pip install --verbose --no-cache-dir torch-cluster
$ pip install --verbose --no-cache-dir torch-spline-conv (optional)
$ pip install torch-geometric
```
### 2.2 グラフデータ
PyGにベンチマーク的なデータセットは用意されているので、今回は **論文の被引用ネットワークを示す[Coraデータセット](https://relational.fit.cvut.cz/dataset/CORA)** を使う。Coraは2708もの論文を含み、それぞれの論文が7つのクラスに分けられている。このデータセットを使って、**各ノード(論文)のカテゴリを予測** する。

```python
from torch_geometric.datasets import Planetoid
dataset = Planetoid(root='/tmp/Cora', name='Cora')
```

### 2.3 GCNレイヤーを使ってみる。
基本的にPyTorchと同じ記法なので、PyTorchを触ったことある方なら特に問題はないかもしれない。PyTorchがわからない場合は[公式チュートリアル(英語)](https://pytorch.org/tutorials/beginner/blitz/tensor_tutorial.html#sphx-glr-beginner-blitz-tensor-tutorial-py)がわかりやすい。

NetクラスにNNの構造とforwardメソッドを記入。その中で単純に ```GCNConv``` を呼び出すだけ。

```python
import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class Net(torch.nn.Module):
    def __init__(self):
        super(Net, self).__init__()
        self.conv1 = GCNConv(dataset.num_node_features, 16)
        self.conv2 = GCNConv(16, dataset.num_classes)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index

        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, training=self.training)
        x = self.conv2(x, edge_index)

        return F.log_softmax(x, dim=1)
```

### 2.4 GCNの学習
学習はPyTorchといたって同じだが、念のため丁寧に触れておく。
学習の時の手順は以下の5つをエポック回だけ繰り返す。

1. [optimizer](https://qiita.com/omiita/items/1735c1d048fe5f611f80)の勾配初期化
2. モデルからの予測値を得る
3. 予測値と正解値で損失をとる
4. 損失のパックプロップ
5. [optimizer](https://qiita.com/omiita/items/1735c1d048fe5f611f80)によるパラメータ更新

つまり、
1. **勾配初期化**
2. **予測値**
3. **損失**
4. **バックプロップ**
5. **更新**

で、コードで書けば、
1. ```optimizer.zero_grad()```
2. ```output=model(input)```
3. ```loss=Loss(output, target)```
4. ```loss.backward()```
5. ```optimizer.step()```

```python
device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model = Net().to(device)
data = dataset[0].to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

model.train() #モデルを訓練モードにする。
for epoch in range(200):
    optimizer.zero_grad()
    out = model(data)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
```

これにて学習が完成する。

### 2.5 評価

```python
model.eval() #モデルを評価モードにする。
_, pred = model(data).max(dim=1)
correct = float(pred[data.test_mask].eq(data.y[data.test_mask]).sum().item())
acc = correct / data.test_mask.sum().item()
print('Acc: {:.4f}' .format(acc))

>>> Accuracy: 0.8150
```

これで評価までできた。
このような簡単なネットワークでもノードのクラスをうまく推測できていることがわかる。

より詳しい説明は[ノートブック](https://github.com/omiita/PyTorchGeometric-Tutorial/blob/master/PyTorch_Geometric_Tutorial.ipynb)をご参照ください。

ちなみに、2層GCNを使ってCoraデータセットのノードをベクトル化させt-SNEで可視化すると以下の図のようになり、**しっかりと同じクラスのデータたちは集まっている**ことがわかる。色が各クラスを表している。

![GCNによるCora可視化](https://imgur.com/EDFutRS.png)
> Kipf, T. et al. "Semi-Supervised Classification with Graph Convolutional Networks" (2017)

## 3. まとめと所感
GCNの簡単な説明とPyTorch Geometricの簡単な使い方について紹介した。
さらなる可能性を秘めているであろうGCNについてこれからも注目していきたい。

**読んで少しでも何か学べたと思えたら 「いいね」 や 「コメント」 をもらえるとこれからの励みになります！よろしくお願いします！**

## 4. 参考

* [Kipf, T. et al. "Semi-Supervised Classification with Graph Convolutional Networks" (2017)](https://arxiv.org/pdf/1609.02907.pdf)
(論文) 現在広く使われるGCNの原型となる論文.

* [PyTorch Geometric Documentation](https://pytorch-geometric.readthedocs.io/en/latest/index.html)
(英語)PyTorch Geometricの公式ドキュメント

* [GRAPH CONVOLUTIONAL NETWORKS](http://tkipf.github.io/graph-convolutional-networks/)
(英語) GCN生みの親のブログ記事。とてつもなく参考にしています。

* [半教師あり学習_Semi-Supervised Learning (Vol.20)](https://products.sint.co.jp/aisia/blog/vol1-20)
半教師あり学習についてわかりやすくまとめてくれている。