[論文]A comprehensive survey on graph neural networkを読んだ

# はじめに
GNN全体をざっくり学びたかったので "A comprehensive survey on graph neural networks"[1]を読んだ。メモ程度に記す。




# 4種類のGNN
GNNは以下の4つに大別することができる。
- Recurrent Graph Neural Networks (RecGNNs)
- Convolutional Graph Neural Networks (ConvGNNs)
- Graph Autoencoders (GAEs)
- Spatial–Temporal Graph Neural Networks (STGNNs)

#  Recurrent Graph Neural Networks (RecGNNs)
GNNの先駆的存在。隣接ノードの情報をもとにのノードの状態を再帰的に更新していく。基本的な更新式として式(1)がある。
```math
\boldsymbol{h}_v^{(t)} = \sum_{u\in N(v)} f(\boldsymbol{x}_v, \boldsymbol{x^e}_{u, v}, \boldsymbol{x}_u, \boldsymbol{h}_u^{(t-1)}) \tag{1}
```

$\boldsymbol{x_v}\in \mathbb{R}^{d}$は頂点$v$の特徴量ベクトル、$\boldsymbol{x_{u, v}^e}\in \mathbb{R}^{c}$は頂点$u$と頂点$v$間のエッジの特徴量ベクトル、$\boldsymbol{h_u}\in \mathbb{R}^{b}$は頂点$u$の隠れ表現である。$\boldsymbol{h}_v^{(0)}$ はランダムな値で初期化されている。$N(v)$は頂点$v$に隣接している全ての頂点の集合である。
安定状態に達するまでこの更新を繰り返す。また、安定状態に収束させるために、$f$は収縮写像(contraction mapping）でなければならない。

# Convolutional Graph Neural Networks (ConvGNNs)
ConvGNNsは**Spectral-Based ConvGNNs** と **Spatial-Based ConvGNNs** の2つに大きく分けられる。Spatial-Basedの方が効率性(efficiency)・汎用性(generality)・柔軟性(flexibility)の点から人気である。

## Spectral-Based ConvGNNs


### 概要
1. グラフ構造から固有ベクトルを抽出
1. 固有ベクトルを使ってグラフデータをスペクトルデータに変換
1. スペクトルデータにフィルター処理してグラフデータへ変換


### グラフ構造から固有ベクトルを抽出
グラフ構造から固有ベクトルを抽出する。
まず正規化グラフラプラシアン (The normailized graph Laplacian matrix）$\boldsymbol{L}\in \mathbb{R}^{n\times n}$は式(2)のように定義される。
```math
\boldsymbol{L} := \boldsymbol{I_n} - \boldsymbol{D}^{-\frac{1}{2}}\boldsymbol{AD}^{-\frac{1}{2}} \tag{2}
```
$\boldsymbol{D}\in \mathbb{R}^{n\times n}$は次数行列、$\boldsymbol{A}\in \mathbb{R}^{n\times n}$は隣接行列をそれぞれ表す。ここで$\boldsymbol{D}$は対角行列なので、$\boldsymbol{D}^{-\frac{1}{2}}$は$\boldsymbol{D}$の対角要素の平方根をとって逆数にしたものとなる[4]。さらに正規化グラフラプラシアン$\boldsymbol{L}$は式(3)のように固有値分解できる。
```math
\boldsymbol{L} = \boldsymbol{U\Lambda U}^{\top} \tag{3}
```
$\boldsymbol{\Lambda}=\operatorname{diag}(\lambda_0, \lambda_1, ..., \lambda_{n-1})\in \mathbb{R}^{n\times n}$は対角成分に$\boldsymbol{L}$の固有値(eigenvalues)$\lambda_i$を持つ対角行列である[5]。$0=\lambda_0 \leq \lambda_1 \leq \cdots \leq \lambda_{n-1}\leq 2$となっている。$\boldsymbol{U}=[\boldsymbol{u_0}, \boldsymbol{u_1}, \dots, \boldsymbol{u_{n-1}}]\in \mathbb{R}^{n\times n}$は$\boldsymbol{L}$の固有ベクトル(eigenvectors)を$\boldsymbol{\Lambda}$の固有値順に並べた行列である。すなわち、$\boldsymbol{\Lambda}$の$i$行目の対角成分にある固有値$\lambda_i$に対応する固有ベクトルが$\boldsymbol{u_i}$である。


### 固有ベクトルを使ってグラフデータをスペクトルデータに変換
通常のフーリエ変換は時系列データをスペクトルデータに変換して、どのスペクトルがよく出てくるか等を利用する。同様に、グラフデータに対しグラフフーリエ変換を行うことでスペクトルデータに変換することができ、どのスペクトルがよく出ているのかがわかるようになる。このスペクトルデータを用いるところが Spectral-Based ConvGNNs の大きな特徴である。

graph signal processing[7]におけるグラフシグナル(graph signal) について考える。グラフシグナル $\boldsymbol{x}=[x_0, x_1, ... x_{n-1}]\in \mathbb{R}^{n}$とは頂点集合$\mathcal{V}$の特徴量ベクトルであり、$x_i$は$i$番目の頂点$v_i$の特徴量を表す。そして、グラフシグナル$\boldsymbol{x}$に対するグラフフーリエ変換(graph Fourier transform)とグラフフーリエ逆変換(inverse graph Fourier transform)は各々式(4)、式(5)のように定義される。
```math
\begin{align}
\mathcal{F}(\boldsymbol{x}) &= \boldsymbol{U}^{\top}\boldsymbol{x} = \boldsymbol{\hat{x}} \tag{4} \\
\mathcal{F}^{-1}(\boldsymbol{\hat{x}}) &= \boldsymbol{U}\boldsymbol{\hat{x}} = \boldsymbol{x} \tag{5}
\end{align}
```
このように$L$の固有ベクトルの行列$\boldsymbol{U}$を用いて、グラフデータ$\boldsymbol{x}$とスペクトルデータ$\boldsymbol{\hat{x}}$の相互変換をすることができる。

### スペクトルデータにフィルター処理してグラフデータへ変換
そしてフィルター(filter)$\boldsymbol{g}\in \mathbb{R}^{n}$を用いたグラフシグナル$\boldsymbol{x}$のグラフ畳み込み(graph convolution)は式(6.1)のように定義され、式(6.3)のように変形できる[9]。
```math
\begin{align}
\boldsymbol{g} *_G \boldsymbol{x}
&:= \mathcal{F}^{-1}(\mathcal{F}(\boldsymbol{g}) \odot \mathcal{F}(\boldsymbol{x})) \tag{6.1}\\
&= \boldsymbol{U}(\boldsymbol{U}^{\top}\boldsymbol{g} \odot \boldsymbol{U}^{\top}\boldsymbol{x}) \tag{6.2}\\
&= \boldsymbol{U}\boldsymbol{g}_{\theta}(\boldsymbol{\Lambda})\boldsymbol{U}^{\top}\boldsymbol{x} \tag{6.3}
\end{align}
```
ここで$\odot$は行列における要素ごとの積(elementwise product)である。グラフ畳み込みは式(6.3)のように、パラメータに$\boldsymbol{\Lambda}$を持つ関数であるフィルター$\boldsymbol{g_{\theta}}$を用いて表すことができる。このフィルター$\boldsymbol{g}_{\theta}$が工夫所となる。


## Spatial-Based ConvGNNs
今の ConvGNNs はほとんどこれにあたる。以下が特徴である[10]。
- 隣接する頂点の情報を考慮して自身の特徴量を更新する
- 学習効率(efficiency)が良い 
    - Spectral-Based は固有値分解とグラフ全体の処理を同時に扱えない
    - Spatial-Based は グラフ上で直接畳み込みができるのでよりスケーラブル
- 汎用性(generality)が良い
    - Spcetral-Based のモデルはグラフの構造に強く依存するので、新しいグラフにはうまく適用できない
    - Spatial-Based は異なる箇所やグラフでの重みを、各頂点で局所的に共有できる
-  柔軟性(flexibility)が良い
    - Spectral-Based は無向グラフしか扱えない
    - Spatial-Based は様々なグラフを扱える


# Graph Autoencoders (GAEs)
GAEs はグラフの構造を潜在表現へ射影し、潜在表現をグラフ情報へデコードする。GAEsは主に、ネットワークの埋め込み表現の学習とグラフ生成に使われる。ネットワークの埋め込み表現は主にlink prediction タスクを解くような学習を行う。グラフ生成は分子構造の生成タスクを解くような学習を行う。

# Spatial–Temporal Graph Neural Networks (STGNNs)
道路交通予測や人間の行動認識など、時間によって変化する空間情報を扱うGNN。



# 参考文献
1. [Wu, Zonghan, et al. "A comprehensive survey on graph neural networks." IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.](https://ieeexplore.ieee.org/abstract/document/9046288?casa_token=HpEmVlxdo08AAAAA:vfr-F7G6HxCaPbmA4k2L8J6s7dXoGDZzvH-im1TPDVvteEOg94SqEHDCRK883dDbHsvaC5OLrjQ)
1. [Cai, Hongyun, Vincent W. Zheng, and Kevin Chen-Chuan Chang. "A comprehensive survey of graph embedding: Problems, techniques, and applications." IEEE Transactions on Knowledge and Data Engineering 30.9 (2018): 1616-1637.](https://ieeexplore.ieee.org/abstract/document/8294302?casa_token=lUBWKgBPm6kAAAAA:ilaGS0jEEMK0coicU8OO6COPLeBzxsol4WqYYzYLHI623GHH5_3U3UqoXrqAp3maROa_5PpfWsQ)
1. [グラフラプラシアンを噛み砕いて噛み砕いて跡形もなくしてみた](https://qiita.com/silva0215/items/0d1d25ef51b6865a6e15)
1. [DavidP.Williamson. "ORIE 6334 Spectral Graph Theory Lecture7". September 13,2016.](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf)
1. [固有ベクトル・固有値とは何か？図と具体例から分かるその意味と使い道](https://atarimae.biz/archives/24166)
1. [【ネットワークの統計解析】第7回　グラフラプラシアン・グラフフーリエ変換を簡単に振り返る](https://buildersbox.corp-sansan.com/entry/2021/05/27/110000)
1. [Xiaowen Dong. "Graph signal processing Concepts, tools and applications in neuroscience". NISOx, Big Data Institute. February 2019.](https://web.media.mit.edu/~xdong/talk/BDI_GSP.pdf)
1. [Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).](https://arxiv.org/abs/1609.02907)
1. [Chen, Xinye. "Understanding spectral graph neural network." arXiv preprint arXiv:2012.06660 (2020).](https://arxiv.org/abs/2012.06660)
1. [第52回SWO研究会チュートリアル資料](https://www.slideshare.net/TakanoriUgai/52swo)