はじめに

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)がある。

\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

概要

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

グラフ構造から固有ベクトルを抽出

グラフ構造から固有ベクトルを抽出する。
まず正規化グラフラプラシアン (The normailized graph Laplacian matrix）$\boldsymbol{L}\in \mathbb{R}^{n\times n}$は式(2)のように定義される。

\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)のように固有値分解できる。

\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)のように定義される。

\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]。

\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。

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