# GCN

GCNは Graph Convolutional Network の略である。"畳み込み"に着想を得てできたNNアーキテクチャーである

## 過去回
[第１回：Graph, GNN](https://hackmd.io/0IwDJxeITPGLyq40EfvT1g)

---

# グラフの畳み込み

## 画像の畳み込み
畳み込みとは数学的な操作である。[参考URL](https://qiita.com/KojiOhki/items/929bf31f78bc679d2b95)

直感的には、畳み込み（CNN）は **フィルター**を使って**特徴**を捉える操作です。


つまり、グラフに畳み込みを適用するという事は、==**グラフの何かしらの特徴をフィルターする事で、グラフの特徴を捉える**== という操作です。

## フーリエ変換とは？


ある関数の時間（もしくは座標）から周波数空間への変換（sin/cosへの分解）操作。

## 画像のフーリエ変換

画像に対してもフーリエ変換の操作は可能。
例えば、Grayスケールにおける隣接する画素値（０〜２５５）の変化は振動と捉える事ができる。



## 畳み込みの際のフーリエ変換のメリット

フーリエ変換と畳み込みの性質して次のような式が成り立つ（* は畳み込み）
関数$f$に対する関数$g$の畳み込み操作は、それぞれをフーリエ変換した関数同士の要素積を再度逆フーリエ変換したものとして表すことができる。



つまり、フーリエ変換できれば、計算量を減らせるのがメリット。

## 画像のフーリエ変換と畳み込み

なので、画像を愚直に畳み込み計算しても良いが、画像をフーリエ変換できれば、単純な要素積として計算できるので、計算が早くなりますよ、ということ。


http://makotomurakami.com/blog/2020/08/03/6370/

## つまり何が言いたいのかというと

**グラフをフーリエ変換できれば、フィルターを使って、CNNと同じようにグラフの特徴マップを抽出できるんじゃないか** という話。


---

# GNNの発展

Spectral based な手法と、Spectral based の手法がある。
**Spectral based** はグラフフーリエ変換して畳み込みをする話。**spartial based** は直感的な手法（[前回の発想](https://hackmd.io/0IwDJxeITPGLyq40EfvT1g)）


今回は**Spectral based** のGNNの話

---

# Spectral based GNN

GCNの大本の考え方。基本的には画像のフーリエ変換を経由する畳み込みと同じ考え方。

## 拡散方程式とグラフラプラシアン

拡散方程式の右辺$\partial^2/\partial x^2$はラプラシアンと呼ばれる作用素である。

同様に、グラフにおけるノードの値の時間発展を考える。
次のように$L$の行列を定義すると

$L$を使って、グラフにおける単位時間あたりのノードの値の変化は次のように定義できる。

$$
\frac{\partial}{\partial t}x(t)=-\kappa L x(t)
$$

式を見比べると、$L$はラプラシアンと同じ操作を示す。そのため、$L$は**グラフラプラシアン**と呼ばれる。

### 補足

グラフは、ある瞬間においてリンクのあるノード間で情報のやり取りが行われると想定できる。
その想定において、この行列は、ある時間$t$における情報量の変化を記述しているとみなせる。
例えば、各ノードが$時間_{t-1}$で$(1,2,3,4)$という情報量を持っている場合、
$$
\left(
\begin{array}{ccc}
2 & -1 & -1 & 0 \\
-1 & 3 & -1 & -1 \\
-1 & -1 & 3 & -1 \\
0 & -1 & -1 & 2 \\
\end{array}
\right)
\left(
\begin{array}{ccc}
1 \\
2 \\
3 \\
4 \\
\end{array}
\right)=
\left(
\begin{array}{ccc}
+2-2-3+0 \\
-1+2-3-4 \\
-1-2+9-4 \\
+0-2-3+8 \\
\end{array}
\right)=
\left(
\begin{array}{ccc}
-3 \\
-6 \\
2 \\
3 \\
\end{array}
\right)
$$
$(-3,-6,2,3)$ という情報量の変化が発生する。
という風に、グラフのノードが、ノード同士で情報のやり取りを行っていると想定すると、そのやり取りは**ラプラシアン行列**で記述できる。


## グラフラプラシアンとフーリエ変換

フーリエ変換とは、時間（座標）空間における振動数空間への変換操作である。
では、グラフにおける振動をどう定義するか。隣り合うノード間との振動と仮定して、次の量$F(x)$について考える。


上記の式は、隣り合うノードの振動の滑らかさ（もしくは激しさ）を表す指標である。
これの$|\boldsymbol{x}|=1$という条件のもとでの停留値$\lambda$（つまり微分＝０）について考えると、

$$
L \boldsymbol{x}= \lambda \boldsymbol{x}
$$

となる（みたい）。つまり、グラフラプラシアン行列の固有値を求めることが、$F(x)$の停留値となる。

**スペクトルグラフ理論によると、グラフラプラシアンの固有関数への展開はフーリエ変換と定義できる。**


グラフフーリエ変換は、グラフラプラシアンの固有関数について掛け合わせた操作と定義できる。


## 考え方の流れのおさらい

フーリエ変換は振動数への変換である
↓
グラフにおける振動を定義する（ノード間の値の差の二乗）
↓
グラフの振動の停留値について解くと（つまり振動数空間への変換を試みる操作に置き換えれる？）、グラフラプラシアンの固有関数への展開とみなせる
↓
グラフラプラシアンの固有値は、グラフの振動におけるフーリエ変換後の振動数を示しており、つまり固有関数はフーリエ変換の操作と定義できる

## つまりグラフ畳み込みとは

グラフにおけるフーリエ変換を定義できたので、グラフの振動数空間におけるフィルターを考えることで、畳み込みを定義できる。



そして、固有ベクトルに対するフィルター係数を学習することで、GraphConvolutionを定義する。


## グラフ畳み込みの一般化

さて、上述の議論では、グラフラプラシアンの１次（あるステップにおけるノードの情報量の変化は１隣接ノードまで）について議論してきた。
では、隣隣接ノードまで考慮すると、グラフラプラシンアはどう変化するか。この場合、単純に二乗する（隣接ノードの情報量の移動を計算したあと、再度その情報を移動させることを計算するので）。


結局、N個先の隣接ノードまでの情報量を計算する際のラプラシアンは、$L^N$と定義できる。
同様にそのラプラシアンの固有ベクトルの展開は、二乗を例とすると

$$
L^2=LL=U\Lambda U^TU\Lambda U^T=U\Lambda I \Lambda U^T=U\Lambda^{2} U^T
$$

となる。なので、N個先の隣接ノードまでを全て考慮したグラフラプラシアンとして定義すると

$$
\boldsymbol{y}=U\Lambda U^T\boldsymbol{x} + U\Lambda^{2} U^T\boldsymbol{x} + ... + U\Lambda^{N} U^T\boldsymbol{x} \\
=U(\sum_{k=1}^{N}\Lambda^{k})U^T\boldsymbol{x} \\
=Ug_{\theta}(\Lambda)U^T \boldsymbol{x}
$$

のように、結局、$L^N$までを考慮した形も同じように記述できる。

---

# ChebNet

いわゆる**GCN**は、ChebNet を簡略化した形式で定義されている。

下記の式について、固有ベクトル$U$を計算するのは計算コストが高いためしたくない。

$$
\boldsymbol{y}=Ug_{\theta}(\Lambda)U^T \boldsymbol{x}
$$

なので、固有ベクトルを無くしたい。そこで、$Ug_{\theta}(\Lambda)U^T$ の部分というのは、$L$に関連する何かだよね、と仮定できるので、次のように変形する。
$$
\boldsymbol{y}=Ug_{\theta}(\Lambda)U^T \boldsymbol{x}=g_{\theta}(L)\boldsymbol{x}
$$

（個人的には思い切りのある変換だと思うが）これで、式から$U$が消えたので、固有ベクトルを計算しなくてよくなる。計算前のグラフラプラシアンを使えば良い。

そこで、$g_{\theta}(L)$を次のように定義する。

$$
g_{\theta}(L)=\sum_{k=0}^{K}\theta_k L^{k}
$$

この$\theta_{k}$が学習パラメータである。固有ベクトルはでてきてないので、そこば計算しなくて良くなる。

（以下をなぜしているのか不明。多分計算が簡単になる？）

[チェビシェフ多項式](https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%93%E3%82%B7%E3%82%A7%E3%83%95%E5%A4%9A%E9%A0%85%E5%BC%8F)を使って、$g_{\theta}$を展開する。



なぜチェビシェフ多項式を使って展開しているのかは不明だが、これがGCNのもとの式。

---

# GCN

ChebNet はK近傍までのノードについて畳み込んでいる。
GCNは、もう$K=1$までで良くない？　と簡略化したもの。


これって実は前回の絵とほぼ同じになる。結局simple な形に戻ったねって話