はじめに

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。

参考文献

Wu, Zonghan, et al. "A comprehensive survey on graph neural networks." IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.
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.
グラフラプラシアンを噛み砕いて噛み砕いて跡形もなくしてみた
DavidP.Williamson. "ORIE 6334 Spectral Graph Theory Lecture7". September 13,2016.
固有ベクトル・固有値とは何か？図と具体例から分かるその意味と使い道
【ネットワークの統計解析】第7回　グラフラプラシアン・グラフフーリエ変換を簡単に振り返る
Xiaowen Dong. "Graph signal processing Concepts, tools and applications in neuroscience". NISOx, Big Data Institute. February 2019.
Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).
Chen, Xinye. "Understanding spectral graph neural network." arXiv preprint arXiv:2012.06660 (2020).
第52回SWO研究会チュートリアル資料