はじめに
本記事は3部作のうち第2部です. GCNの導入や記号の定義などは前回の記事をご参照ください.
GNNまとめ(1): GCNの導入 - Qiita
前回の記事でSpatial GCNの導入までを書いたので, 今回は様々なSpatial GCNについて重要と思われるものをかいつまんで簡単に紹介します.
すべての論文を読んだわけではないので, 間違いなどがございましたら遠慮なくご指摘いただけると助かります. また, 各アルゴリズムにつき図を1枚貼っていますが, これは説明のためというより見た目で区別しやすくするためです.
[1]より引用.
GCN
GCNは, CNNのようにフィルタの畳込みをグラフ上で行うことでグラフやノードの潜在ベクトルを得る方法です.
畳込みの定義の仕方にはグラフフーリエ変換を用いるアプローチとより直接的なアプローチの2種類がありますが, ここでは後者について説明します.
Spatial GCN
Neural Fingerprint
Convolutional Networks on Graphs for Learning Molecular Fingerprints
Neural Fingerprint (NFP) は, 分子の潜在ベクトル(molecular fingerprint)を得るためのアルゴリズムです.
原子価が5までであることを利用して, 注目しているノードの次数ごとにフィルタを用意しています.
第$l$層での計算は次のようになります. $k$は周辺ノードをどの距離まで考慮するかを表すパラメータです.
\boldsymbol{h}_i^{l+1} = \rho \Biggl( \sum_{j \in \mathcal{N_k}(i)} \boldsymbol{h}_i^l \boldsymbol{\Theta}_d^l \Biggr)
この式がGCN(Kipf+)と似ていることに注意してください. ラプラシアン行列を次数で正規化する代わりに, 次数によって異なるフィルタを利用しています.
PATCHY-SAN
[Learning Convolutional Neural Networks for Graphs](https://arxiv.org/abs/1605.05273)
PATCHY-SANは, ノードに順番をつけることでグラフをテンソルに変換し, あとはCNNと同じように処理するという, (名前とともに)ユニークなアルゴリズムです. どなたか名前の由来を教えてください.
ノードに順番を割り振るのには, グラフ同士の類似度を測るヒューリスティクスであるWeisfeiler-Lehmanカーネルを使います(詳しくは[4]などを参照).
この順番に従って各ノードから近傍ノード$K$個を集めることで, $(N\times K \times F^V)$のテンソルを作ることができます.
テンソルができてしまえば画像と同じように扱えるので, 任意のCNNに入力することができます.
この手法のポイントは「順番付け」にあります. これによって構造的に似たノードがテンソル上で近い位置に来るようになるのですが, 全体としての性能がこのヒューリスティクスに強く依存してしまうという問題があります.
DCNN
Diffusion-Convolutional Neural Networks
DCNN (diffusion-convolutional neural network) は, 長さ$K$の遷移行列のべき級数で畳み込みを定義するアルゴリズムです.
$\boldsymbol{\Theta}^l$を対角行列として, 第$l$層での計算を次のように定義します.
\boldsymbol{H}^{l+1} = \rho(\boldsymbol{P}^K\boldsymbol{H}^l\boldsymbol{\Theta}^l)
MPNN
[Neural Message Passing for Quantum Chemistry](https://arxiv.org/abs/1704.01212)
計算の高速化と汎用性(構造の異なるグラフにも適用できる)を両立するためのフレームワークとして提案されたのがMPNN (message passing neural network) です. message passingの考え方はとても重要で, 他の手法でもしばしば登場します.
MPNNでは, 第$l$層での学習可能なメッセージ関数(message function) を$\mathcal{F}^l$, 頂点更新関数(vertex update function) を$\mathcal{G}^l$として, 次のようにノードの潜在ベクトルを更新します(message passing phase).
\begin{eqnarray}
\boldsymbol{m}_i^{l+1} &=& \sum_{j \in \mathcal{N}(i)} \mathcal{F}^l(\boldsymbol{h}_i^l, \boldsymbol{h}_j^l, \boldsymbol{F}_{i,j}^E)\\
\boldsymbol{h}_i^{l+1} &=& \mathcal{G}^l(\boldsymbol{h}_i^l, \boldsymbol{m}_i^{l+1})
\end{eqnarray}
第1式では隣接ノードとエッジの特徴から注目ノードに向かう「メッセージ」$\boldsymbol{m}^l$の和を計算し, 第2式ではそのメッセージを使って潜在ベクトルを更新します.
グラフ全体の潜在ベクトルを得る場合は, 次の式を利用します(readout phase).
\boldsymbol{\hat{y}} = \mathcal{R}([\boldsymbol{h}_i^\mathrm{T} | i \in V])
MPNNをこのように定義すると, これまでに紹介したGGS-NN, Spectral GCN, GCN(Kipf+), NFPなどはMPNNの特殊な例と捉えることができます.
といってもよくわからないので, ここではGGS-NNの例を挙げます. $\mathcal{F}, \mathcal{G}$を次のように定義するとGGS-NNになるので, 前回の記事の復習も兼ねて確認してみてください.
\begin{eqnarray}
\mathcal{F}(\boldsymbol{h}_i, \boldsymbol{h}_j, \boldsymbol{F}_{i,j}^E) &=& \theta_{e_{ij}} \boldsymbol{h}_j\\
\boldsymbol{z}_i &=& \rho(\boldsymbol{\Theta}_z[\boldsymbol{h}_i, \boldsymbol{m}_i])\\
\boldsymbol{r}_i &=& \rho(\boldsymbol{\Theta}_r[\boldsymbol{h}_i, \boldsymbol{m}_i])\\
\boldsymbol{\tilde{h}}_i &=& \tanh{\boldsymbol{\Theta}_h[\boldsymbol{r}_i\odot \boldsymbol{h}_i, \boldsymbol{m}_i]}\\
\mathcal{G}(\boldsymbol{h}_i, \boldsymbol{m}_i) &=& (1-\boldsymbol{z}_i)\odot \boldsymbol{h}_i + \boldsymbol{z}_i \odot \boldsymbol{\tilde{h}}_i
\end{eqnarray}
GraphSAGE
Inductive Representation Learning on Large Graphs
GraphSAGE もMPNNと同様にフレームワークを提案したものです. SAGEはSAmple and aggreGatEからとったものらしいですが, わかりにくいですね.
順序不変的な集約関数$\mathrm{AGGREGATE}$を用意して, 次のように潜在ベクトルを更新します.
\begin{eqnarray}
\boldsymbol{m}_i^{l+1} &=& \mathrm{AGGREGATE}^l(\mathrm{\{} \boldsymbol{h}_j^l, \forall j \in \mathcal{N}(i)\mathrm{\}} )\\
\boldsymbol{h}_i^{l+1} &=& \rho(\boldsymbol{\Theta}^l[\boldsymbol{h}_i^l, \boldsymbol{m}_i^l])
\end{eqnarray}
$\mathrm{AGGREGATE}$としては, element-wiseな平均, LSTM, 最大値プーリングのような関数の3種類が提案されています.
MoNet
[Geometric deep learning on graphs and manifolds using mixture model CNNs](https://arxiv.org/abs/1611.08402)
MoNet (mixture model network) はグラフに擬似座標を導入し, 座標に従った重みによって畳み込みを定式化しました.
DCNNはMoNetの一例になります.
GN
[Relational inductive biases, deep learning, and graph networks](https://arxiv.org/abs/1806.01261)
GN (graph network) はGCNとGNNを一般化したフレームワークで, ノード, エッジ, グラフそれぞれの潜在ベクトル $\boldsymbol{h}_i$,
$\boldsymbol{e}_{ij}$, $\boldsymbol{z}_i$
を学習します.
具体的には, 集約($\mathcal{G}$)と更新($\mathcal{F}$)を次のように行います.
\begin{eqnarray}
\boldsymbol{m}_i^l &=& \mathcal{G}^{E \rightarrow V}( \mathrm{\{} \boldsymbol{h}_j^l, \forall j \in \mathcal{N}(i)\mathrm{\}} )\\
\boldsymbol{m}_V^l &=& \mathcal{G}^{V \rightarrow G}( \mathrm{\{} \boldsymbol{h}_i^l, \forall v_i \in V \mathrm{\}} )\\
\boldsymbol{m}_E^l &=& \mathcal{G}^{E \rightarrow G}( \mathrm{\{} \boldsymbol{h}_{ij}^l, \forall (v_i, v_j) \in E \mathrm{\}} )\\
\boldsymbol{h}_i^{l+1} &=& \mathcal{F}^V( \boldsymbol{m}_j^l, \boldsymbol{h}_i^l, \boldsymbol{z}^l)\\
\boldsymbol{e}_{ij}^{l+1} &=& \mathcal{F}^E( \boldsymbol{e}_{ij}^l, \boldsymbol{h}_i^l,\boldsymbol{h}_j^l, \boldsymbol{z}^l)\\
\boldsymbol{z}^{l+1} &=& \mathcal{F}^G( \boldsymbol{m}_E^l, \boldsymbol{m}_V^l, \boldsymbol{z}^l)
\end{eqnarray}
GAT
[Graph Attention Networks](https://arxiv.org/abs/1710.10903)
GAT (graph attention network) は, 隣接ノードを畳み込む時の重み$\alpha_{ij}^l$をAttentionで決めます.
\begin{eqnarray}
\boldsymbol{h}_i^{l+1} &=& \rho \Biggl( \sum_{j\in \mathcal{N}(i)} \alpha_{ij}^l \boldsymbol{h}_i^l \boldsymbol{\Theta}^l \Biggr) \\
\alpha_{ij}^l &=& \underset{k\in \mathcal{N}(i)}{\mathrm{softmax}} ~ \mathrm{LeakyReLU}(\mathcal{F}(\boldsymbol{h}_i^l\boldsymbol{\Theta}^l, \boldsymbol{h}_j^l\boldsymbol{\Theta}^l))
\end{eqnarray}
$\mathcal{F}$は小規模な全結合ニューラルネットです.
JK-Net
[Representation Learning on Graphs with Jumping Knowledge Networks](https://arxiv.org/abs/1806.03536)
JK-Net (jumping knowledge network) はResNetのような残差ブロックを利用したネットワークです. 図のように, 各層の出力$\boldsymbol{h}_i^l$を最終層の出力$\boldsymbol{h}_i^L$に連結してから集約します. これによって, タスクごとに適切な範囲で周辺ノードの特徴を取り込むことができます.
\boldsymbol{h}_i = \mathrm{AGGREGATE}(\boldsymbol{h}_i^0,...,\boldsymbol{h}_i^L)
集約関数$\mathrm{AGGREGATE}$としては, concatenation, 最大値プーリング, LSTMが用いられます.
R-GCN
[Modeling Relational Data with Graph Convolutional Networks](https://arxiv.org/abs/1703.06103)
R-GCN (relational GCN) は知識ベースのように多数の種類があるエッジの特徴を利用できるアルゴリズムです.
次の式のように, エッジの種類ごとに異なる重み行列$\boldsymbol{W}^{l}_{r}$をかけてから足し合わせます.
\boldsymbol{h}_i^{l+1}=\rho\Bigl(\sum_{r\in\mathcal R}\sum_{j\in\mathcal N^r(i)}\frac{1}{\mathcal c_{i,r}}\boldsymbol{W}^{l}_{r}\boldsymbol{h}_j^l+\boldsymbol{W}_0^l\boldsymbol{h}_i^l\Bigr)
おわりに
今回は, 様々なSpatial GCNを紹介しました.
次回はAutoencoder, GAN, 強化学習, 動的グラフなど発展的な内容を扱います.
参考文献
[1] Z. Zhang et al., Deep Learning on Graphs: A Survey, arXiv, 2018.
本記事は主にこちらの論文をベースにしています. 3本の中で一番わかりやすく感じました.
[2] J. Zhou et al., Graph Neural Networks: A Review of Methods and Applications, arXiv, 2018.
[3] Z. Wu et al., A Comprehensive Survey on Graph Neural Networks, arXiv, 2019.
[4] Learning Convolutional Neural Networks for Graphs
PFN秋葉さんによるPATCHY-SANの解説スライドです. WLカーネルの解説もあります.