はじめに
近年、グラフ構造に対するDeep lerningとして、Graph Convolutional Networksを用いた手法が注目されています。GCNは直感的にも分かりやすく、ライブラリを使って学習させる分には問題はありません。ただし、グラフ畳み込みとはなんなのか、通常の畳み込みとどう関連づいているのかが個人的に分かりづらかったので、通常の畳み込みとの関連を意識して、グラフ畳み込みを大雑把に導出してみました。
※ 筆者も勉強中につき間違い等もあると思いますが、ご容赦ください。
導出の流れ
グラフ畳み込みは一般の畳み込みの類推から定義します。一般の畳み込みはフーリエ変換と関連があり、フーリエ変換はラプラシアンと関連があります。つまり、グラフに対するラプラシアンを導出できると関連を辿っていくことでグラフに対するフーリエ変換が導出でき、ひいてはグラフに対する畳み込みを導出することができます。
以下でラプラシアンから順にみていきます。
- ラプラシアン -> フーリエ変換 -> 畳み込み
- グラフラプラシアン -> グラフフーリエ変換 -> グラフ畳み込み
ラプラシアン
ラプラシアンは勾配の発散でした。ではグラフに対する勾配と発散とはなんでしょうか？
グラフの勾配はグラフの接続行列の転置、グラフの発散は接続行列として表現できます。接続行列についてとグラフの勾配/発散のイメージは以下がわかりやすいです。
[グラフラプラシアンを噛み砕いて噛み砕いて跡形もなくしてみた] (https://qiita.com/silva0215/items/0d1d25ef51b6865a6e15)
よって、グラフラプラシアン$L$は接続行列$B$を用いて以下のように書けます。
$$ L=BB^T $$
フーリエ変換
複素正弦波$e^{-jωt}$にラプラシアンを作用させると以下のようになります。
$$\frac{∂^2}{∂t^2}e^{-jωt} = -ω^2e^{-jωt}$$
これはラプラシアンの固有関数が$e^{-jωt}$であるとみることができます。ラプラシアンの固有関数を用いて一般の信号$f(t)$に対するフーリエ変換は
$$F(ω)=\sum_{t=-∞}^{∞} f(t)e^{-jωt}\ $$
とかけます。
正方行列であるグラフラプラシアンを固有値分解すると、固有値を対角成分にもつ行列$A$と固有ベクトルからなる行列$U$を用いて
$$L=UAU^T$$
とかけます。
一般のフーリエ変換の式における時間$t$をノード番号n(max=N-1)で置き換えると
$$F(ω)=\sum_{n=0}^{N-1} f(n)e^{-jωn}\ $$
となります。これは各ノードにおける信号と固有関数の値の積をノードN個分合計した値であり、各ノードにおける固有関数の値を、各ノードに対応する固有ベクトルの値に置き換えて考えてみます。すると、グラフ上の信号を
$$x=\{f(0),...,f(N-1) \}$$
として、$x$に対するグラフフーリエ変換は
$$F_G[x]=U^Tx$$
とできます。また、逆フーリエ変換は以下のように書けます。
$$F_G^{-1}[F_G[x]]=UU^Tx=x$$
この辺りは以下サイトが参考になると思います。
[GNNまとめ(1): GCNの導入] (https://qiita.com/shionhonda/items/d27b8f13f7e9232a4ae5)
畳み込み
畳み込み定理より以下の式が成り立ちます。
$$F_G[xy]=F_G[x]\odot F_G[y]$$
よって、
$$xy=F_G^{-1}[F_G[x]\odot F_G[y]]=U((U^Tx)\odot (U^Ty))$$
とかくことができ、この式がグラフ上の信号$x$と、フィルタ$y$を畳み込んだ結果となります。
おわりに
グラフ畳み込みを導出してみました。正直、上の式を知らなくてもGCNを使った機械学習で困ることはほぼないと思いますがなんとなくスッキリしてもらえたなら嬉しいです。
さらなる勉強用
https://qiita.com/shionhonda/items/d27b8f13f7e9232a4ae5
https://masashi16.hatenablog.com/entry/2019/08/13/135753
https://www.slideshare.net/yukihirodomae/graph-convolution