# グラフニューラルネットワーク 第３章
## 3.1 メッセージ伝達による定式化
### 3.1.1 メッセージ伝達型グラフニューラルネットワーク
* **設定 （頂点埋め込みの計算）**
* 入力 ： 頂点特徴量付きグラフ $G = (V, E, X)$
* V : 頂点集合
* E : 辺集合
* X : 頂点特徴量（ノード毎に持つ）
* 出力 ： 周辺のノードによって加工された頂点の埋め込み $Z = R ^{n \times d}$
埋め込みを獲得するまでの式を見てみると
①初期値の獲得
$$h^{(0)}_v = {X}_v ( \forall v \in V)$$
②近傍集合のノードを使ってなんか集約する（更新式）
$$h^{(l + 1)}_v = f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\})$$
ここで出てくる$\{\{\}\}$は、多重集合（重複したラベルのノードであっても、別々のノードとして扱う）である。
③何回か（$L$ 回）更新したあとの $h$ を埋め込みとして獲得
$$z_v = h^{(L)}_v$$
$h$ のおでこについてる $l$ だの $L$ だのはニューラルネットワークにおける何層目、というのに相当する。
わざわざ$f^{集約}_{\theta , l+1}$ とおでこに"集約"とつけている関数は集約関数と呼び、主にはこの$f^{集約}_{\theta , l+1}$ の中身を色々いじることによってさまざまなグラフニューラルネットワークとして定義できる。
集約関数を$L$ 回実行して得られる埋め込みを、推論結果$Z$ とする。ここで、$Z$ は $n$個のノードの特徴量を並べたもの。
$$Z = [h^{(L)}_1 , h^{(L)}_2, ... ,h^{(L)}_n]^{\top} \in \mathbb{R}^{n \times d}$$
全部で $L$ 層のグラフニューラルネットワークを通して、埋め込み特徴量$Z$ を手に入れる過程は
1. $h^{(0)}_v = \boldsymbol{X}_v ( \forall v \in V)$
2. **for** $l = 0,1, ... ,L-1$ **do**
3. $\quad \quad h^{(l + 1)}_v = f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\})$
4. **end**
5. $Z = [h^{(L)}_1 , h^{(L)}_2, ... ,h^{(L)}_n]^{\top} \in \mathbb{R}^{n \times d}$
6. Return $Z$
と書ける。
ここからは、$f^{集約}_{\theta , l+1}$ をどう定義するか、いくつかのパターンを紹介していくことになる。
とその前に、（通常の）ニューラルネットワークとの対応について小話をひとつ。
### 3.1.2 通常のニューラルネットワークは特殊例
言い方を変えれば、基本的にはニューラルネットワークは層内の結合を想定しないので、
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\})$$
こいつの右側の引数がないものをあらためて関数 $g$ と考えれば
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}) = g_{l+1}(h^{(l)}_v)$$
であり、この$g$ は通常のニューラルネットワークとしてみることができるらしい。
※これは、グラフニューラルネットワークの推論と通常のニューラルネットワークの対応を論じたものだが、本当にそうみるべきなのだろうか・・・？
>
> （余談）
> 例えば、ニューラルネットワークは、単層の場合、入力$\mathbf{x}$に対する（ほぼ）線形変換として
> $g(\mathbf{x}) = \mathbf{W}{\mathbf{x}} + \mathbf{b}$
> のようにかけるのだが、バイアスを無視しておけば、ここでは$\mathbf{W}$ によって$\mathbf{x}$がある変換を行われる構造となっている。
> 実際、これをメッセージ伝達と同様の演算にすることは可能なはずで、$\mathbf{x}$をノード特徴量と見立てて、それを周辺ノードの特徴量を反映した$\mathbf{W}$として準備すれば、グラフニューラルネットワークの一層分となるような計算は可能なような気がしている。
ただ、こうすると結局ノード間の関係を可変パラメータの重みとして保持するしかないので、特徴量そのものを返還させるという謎な学習になり、学習がうまくできないんじゃないかということで、そういう置き方は意味がないということなのかもしれない。後で試す。
>
## 3.2 具体的なアーキテクチャ
### 3.2.1 グラフたたみ込みネットワーク（GCN）
計算のため、自己ループを追加する。（孤立したノードもそのまま計算できるため、という意味合いもある）
＋ 自身のノード特徴量を失うのを避けるため
GCNは、以下の集約関数で定式化される。
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}) = \sigma \Bigl( \sum_{u \in N(v)} \frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}}\mathbf{W}^{(l+1)}h^{(l)}_u \Bigr)$$
ここで、$\sigma$ は活性化関数で、いつぞや解説されていたが、大方使われることが多いのはLeaky ReluやらELUやら。
$|N(u)|$はノード$u$に対する次数に相当する。つまり、$h_v$が巨大にならないように、値を抑えているのが分数の部分。
式をよく見てみると、隣接する頂点$u \in N(v)$に関する特徴量を足し合わせて新たな中間表現$h_v$を得る。
ちなみになぜ$u$と$v$の次数の平方根を使うのか、$|N(v)|$ではだめなのか？というのはもっともで、別に$|N(v)|$でも良いのだが、
ノード感が与える影響を対称化するように、それぞれのノードの字数の平方根を使うらしい。
（本の流れ的には推論の定式化からドーンと出てくるので、この辺が納得いかないが、グラフニューラルネットワークの原著やサーベイ論文では、行列計算から導出しているので、そっちから導出すれば不自然ではないし、最近だとサーベイ論文上では$|N(v)|$で書かれていたりする）
参考：https://www.sciencedirect.com/science/article/pii/S2666651021000012
あと、サーベイ論文での流れの通り、Spectral Approachesから畳み込みの意味を考えると、よりわかりやすくなるらしいが・・・６章の話題に期待。
ここで、グラフたたみ込みネットワークを行列形式で表すことを試みる。 $\mathbf{H}^{(l)} = [h^{(l)}_1, ... , h^{(l)}_n]^{\top} \in \mathbb{R}^{n \times d_l}$として、全ての頂点の中間表現（特徴量）を行列で表現しておく。隣接行列$\mathbf{A}$を準備しておけば、特徴量$\mathbf{H}^{(l)}$と隣接行列$\mathbf{A}$の積は、あるノードと繋がっているノードたちの特徴量を足し算したもの、となる。
例えば、
こんな感じである。ここに、グラフニューラルネットワークの重みである$\mathbf{W}$をかけてやればよい。
しかし、各ノードの次数が大きく、かつグラフも巨大になっていけば、特徴量はこの演算を行うごとにどんどんデカくなっていってしまう。しかも自己ループまで追加するもんだから、$\mathbf{A}\mathbf{H}^{(l)}$は巨大になることが明らかである。
そこで、隣接行列の各成分を次数行列で正規化したものを考えることにする。具体的には、$\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$で正規化した隣接行列$\mathbf{\hat{A}}$を代わりに使えば良い。
$\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$の各成分は、各行が自身のノード$v$の次数の平方根と、隣接しているあるノード$u$の次数の平方根をかけたものに対応しているので（画像参照）、
$\mathbf{\hat{A}}\mathbf{H}^{(l)}$のノード$v$について考えれば
$$(\mathbf{\hat{A}}\mathbf{H}^{(l)})_v = \sum_{u \in N(v)} \frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}}h^{(l)}_u$$
である。
話を戻せば、$\mathbf{A}\mathbf{H}^{(l)}$あらため、$\mathbf{\hat{A}}\mathbf{H}^{(l)}$に$\mathbf{W}^{(l+1)}$をかけて、活性化関数$\sigma$ を通せばグラフ畳み込みネットワークの定式化を行列で表記することができて
$$\mathbf{H}^{(l+1)} = \sigma (\mathbf{\hat{A}}\mathbf{H}^{(l)}\mathbf{W}^{(l+1)}) $$
と書くことができる。
### 3.2.2 グラフ注意ネットワーク（GAT）
注意機構（Attention）を用いたグラフニューラルネットワークのことで、グラフたたみ込みの際には、隣接頂点の重み付けが次数行列で行われていたのを、データに応じた重み付けになるように定式化したものとなる。
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}) = \sigma \Bigl( \sum_{u \in N(v)} \alpha^{(l+1)}_{vu}\mathbf{W}^{(l+1)}h^{(l)}_u \Bigr)$$
グラフ畳み込みにおける正規化の項が、$\alpha$ に変わったというだけのこと。
$alpha$は、ベクトルの連結を$Concat(a;b)$と表すと
（原文中では、$||$が使われている）
$$\alpha^{(l+1)}_{vu} = \frac{exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\tilde{h}^{(l)}_v ; \tilde{h}^{(l)}_u)\bigr)\bigr)}{\sum_{w \in N(v)}exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\tilde{h}^{(l)}_v ; \tilde{h}^{(l)}_w)\bigr)\bigr)} \in \mathbb{R}$$
ここで、$\tilde{h}^{(l)}_v = \mathbf{W}^{(l+1)}_a h^{(l)}_v$であり、$\mathbf{W}^{(l+1)}_a$はアテンション専用の重みである。
個人的には、わかりにくいのでこっちで表記したい。
$$\alpha^{(l+1)}_{vu} = \frac{exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_u)\bigr)\bigr)}{\sum_{w \in N(v)}exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_w)\bigr)\bigr)} \in \mathbb{R}$$
実際、$Concat$はその結果をその名前の通り連結しておくだけで、$$\mathbf{W}^{(l+1)}_a h^{(l)}_v \in \mathbb{R}^{f^{集約}}$$
であり、
$$Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_u) \in \mathbb{R}^{2f^{集約}}$$
であるから、$\mathbf{a}^{(l+1)} \in \mathbb{R}^{2f^{集約}}$とすれば、$$\mathbf{a}^{(l+1)\top}Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_u)$$ はスカラー値を取る。あとはその計算が$N(v)$の個数だけされるので、和で平均化するだけ、つまり、ぐちゃぐちゃ書いてあるけど、
$\alpha^{(l+1)}_{vu}$ はあるノード$v$に隣接するノード$u \in N(v)$からの情報をどれぐらい重要視するのか、ということを、$\mathbf{a}^{(l+1)}$との積によって計算しているという見方ができる。（自分のノードの情報を重要視するか、隣接ノードの情報を重要視するかのバランスを見ているとも言える）
### 余談
アテンションについては、これをマルチヘッド（複数並べる形式）型アテンションにして、計算すると精度が上がるという主張が古来Transformerより語られてきていて、グラフ注意ネットワークについても同様のことが言えるらしいが、この話はTransformerとグラフ注意ネットワークにおいて、似たようなことが計算上起きているぞ、ということを理解しないといけないので、一旦保留
（てか、グラフニューラルネットワークの性質上入れている自己ループのせいで、セルフアテンションを入れてる気がする。結果ややこしく見える）
### 3.2.3 ゲート付きグラフニューラルネットワーク（GGNN）
※全然使ってる人を見ません
以下で定式化した。
$$f^{集約}_{(l+1)}\bigl(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}\bigr) = (1 - z^{(l+1)}_v)\odot h^{(l)}_v + z^{(l+1)}_v \odot \tilde{h}^{(l+1)}_v$$
$$\tilde{h}^{(l+1)}_v = tanh \bigl( \mathbf{W}m^{(l+1)}_v + \mathbf{U}\bigl(r^{(l+1)}_v \odot \tilde{h}^{(l+1)}_v\bigr)\bigr)$$
$$r^{(l+1)}_v = \sigma(\mathbf{W}^{(r)}m^{(l+1)}_v + \mathbf{U}^{(r)}h^{(l)}_v)$$
$$z^{(l+1)}_v = \sigma(\mathbf{W}^{(z)}m^{(l+1)}_v + \mathbf{U}^{(z)}h^{(l)}_v)$$
$$m^{(l+1)}_v = \sum_{u \in N(v)} h^{(l+1)}_u + b$$
多分紹介以上に何かする必要はない気がするが（使わないから）、$m$をメッセージだと思えば、
周辺ノードからの集約情報をまとめた$m$をポジティブに捉えるか、ネガティブに捉えるかをいっぱいいっぱい式にしている感じ。LSTMが流行ってた頃だと、忘却ゲートと記憶ゲートという形式で習ったことはあるかもしれないが、忘却する割合を$r$で決定して、新たに記憶する割合を$z$で決定する。
そこにメッセージ伝達をねじ込んだのが、GGNNというわけだが、それぞれのゲートに無理やりメッセージをめり込ませているので、学習が大変そうではある。
参考：）https://ieeexplore.ieee.org/abstract/document/8053243/
### 3.2.4 単純グラフたたみ込み（SGC）
行列形式で書いたグラフたたみ込みネットワーク
$$\mathbf{H}^{(l+1)} = \sigma (\mathbf{\hat{A}}\mathbf{H}^{(l)}\mathbf{W}^{(l+1)}) $$
の活性化関数を取り去ったもので、グラフたたみ込みネットワークにおいて最終的な埋め込み$\mathbf{Z}$を獲得する過程を
$$\mathbf{Z} = \sigma\bigl(\mathbf{\hat{A}}\sigma\bigl(...\sigma\bigl(\mathbf{\hat{A}}\mathbf{X}\mathbf{W}^{(1)}\bigr)\mathbf{W}^{(2)}...\bigr)\mathbf{W}^{(L)}\bigr)$$
で表せば、その活性化関数を取り除いたものは$\sigma\bigl(\bigr)$が消え去っていくだけなので
$$\mathbf{Z} = AAAAAXWWWWWW$$
みたいになる。もうちょっと真面目に書くと
$$\mathbf{Z} = \mathbf{\hat{A}}^{(1)}\mathbf{\hat{A}}^{(2)}...\mathbf{\hat{A}}^{(L)}\mathbf{X}\mathbf{W}^{(1)}\mathbf{W}^{(2)}...\mathbf{W}^{(L)}$$
となるので、$\mathbf{\hat{A}}^{(1)}\mathbf{\hat{A}}^{(2)}...\mathbf{\hat{A}}^{(L)} = \mathbf{\hat{A}}^{L}$, $\mathbf{W}^{(1)}\mathbf{W}^{(2)}...\mathbf{W}^{(L)} = \mathbf{W}^{L}$とおけば、
$$\mathbf{Z} = \mathbf{\hat{A}}^{L}\mathbf{X}\mathbf{W}^{L}$$
である。以上。
### 3.2.5 同類・異類選好グラフたたみ込みネットワーク（HHGCN -> $H_2GCN$）
異類選好型のグラフにうまく対応するために、いろいろ工夫をしましょうということ。式は単純で、工夫についても、まあそうだろうな感がある。
① 集約時の工夫
集約を行う際に、自身のノードに関する表現と、近傍集合から得られる表現を区別して集約するようにする。具体的には、再度$Concat$を登場させて
$$h^{(l+1)}_v = Concat\Bigl(h^{(l)}_v, \sum_{u \in N(v)}\frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}}h^{(l)}_u\Bigr)$$
のように、自身のノードの情報と近傍のノードの情報を連結して保存する仕組みを取り入れる。
② １回の集約に際し、近傍の近傍（ご希望ならさらに近傍）の情報も連結して保持する
①で得た$\sum_{u \in N(v)}\frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}}h^{(l)}_u$を$g(\{\{h^{(l)}_u | u \in N(v)\}\})$とし、ノード$v$の近傍のさらに近傍を$N_2(v)$とし、以後$N$の下側の添字をグラフのホップ数（ウォーク回数）とすると、集約時に３ホップ先までの情報を連結させた結果は
$$h^{(l+1)}_v = Concat\Bigl(h^{(l)}_v, g(\{\{h^{(l)}_u | u \in N(v)\}\}), g(\{\{h^{(l)}_u | u \in N_2(v)\}\}), g(\{\{h^{(l)}_u | u \in N_3(v)\}\})\Bigr)$$
と表すことができる。実際、異類選好グラフでは、同類のノードが数ホップ先まで見つからないケースを想定して、集約する範囲を広げておくことが重要とのこと。（意味はわかるけど実際に使うケースがあるのかは確かめてみたい。）
③ 中間層のバイキング形式
基本的にグラフニューラルネットワークは、最終的な埋め込み$\mathbf{Z}$を獲得する。$\mathbf{Z}$は基本的には$L$回の集約関数の計算を経て手に入れた最終的なノード特徴量$h^{(L)}_v$をならべた$\mathbf{H}^{(L)}$だが、$\mathbf{H}^{(1)}$や$\mathbf{H}^{(2)}$など、途中結果もどんどん使おうよ、ということである。つまり
$$\mathbf{Z} = Concat\bigl(\mathbf{H}^{(1)},\mathbf{H}^{(2)},....,\mathbf{H}^{(L)}\bigr)$$
を獲得するようにして、最後タスクを解くときに$\mathbf{H}^{(1)}$から$\mathbf{H}^{(1)}$好きなものを使ってね、というものである。つまり分類だろうと回帰だろうと、特徴量をバイキング形式で選好するネットワークを構築するということである。
Kaggleでいつか見た、Stackingみたいな考え方なのだろうか・・・
まあ実際、Transformerのマルチヘッドアテンション（複数頭注意！）も似たようなもので、多角的に入力データを捉える構造を有することで、単語間のつながりに多様なパターンを生成するような方式と似ているのかな、ぐらいの感想。
### ここまでのまとめ
* グラフニューラルネットワークの１層分の処理は、ノード特徴量を、近傍集合の情報を得て更新することになる。$L$ 層分の処理結果を埋め込み$\mathbf{Z}$として獲得する。その処理は、あるノード$v$に対する集約関数として
$$h^{(l + 1)}_v = f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\})$$
のように記述される。
* グラフたたみ込みネットワークは、集約関数を、あるノードが近傍ノード集合から情報を得るという形を素直に式にしたものである。
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}) = \sigma \Bigl( \sum_{u \in N(v)} \frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}}\mathbf{W}^{(l+1)}h^{(l)}_u \Bigr)$$
ここで出てくる、ノード及びその近傍集合の次数の平方根は、正規化項であるが、これは、グラフたたみ込みネットワークを行列で表現するとわかりやすい。
$$\mathbf{H}^{(l+1)} = \sigma (\mathbf{\hat{A}}\mathbf{H}^{(l)}\mathbf{W}^{(l+1)}) $$
隣接行列$\mathbf{A}$を正規化しないと、層を経るごとに値が巨大化していくので、代わりに正規化項を入れた隣接行列$\mathbf{\hat{A}} = \mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$を用いる。
また、単純たたみ込みグラフニューラルネットワークは、活性化関数を使わないシンプルなもので、活性化関数がないため、行列形式では、$\mathbf{A}$と${\mathbf{W}}$をひとまとめに書けて、$\mathbf{\hat{A}}^{(1)}\mathbf{\hat{A}}^{(2)}...\mathbf{\hat{A}}^{(L)} = \mathbf{\hat{A}}^{L}$, $\mathbf{W}^{(1)}\mathbf{W}^{(2)}...\mathbf{W}^{(L)} = \mathbf{W}^{L}$とおけば、
$$\mathbf{Z} = \mathbf{\hat{A}}^{L}\mathbf{X}\mathbf{W}^{L}$$
で表すことができる。そしてあんまり性能が落ちないらしい。
* グラフ注意ネットワークは、近傍ノード集合からの情報を重視するか、自身の情報を重視するかをAttention（注意機構）で調整できるように$\alpha$という係数を導入したものである。学習するパラメータは増えてしまうが、グラフを直接操作せずに、タスクの処理に重要そうな情報を残すための戦略として有効らしい。
$$f^{集約}_{\theta , l+1}(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}) = \sigma \Bigl( \sum_{u \in N(v)} \alpha^{(l+1)}_{vu}\mathbf{W}^{(l+1)}h^{(l)}_u \Bigr)$$
$$\alpha^{(l+1)}_{vu} = \frac{exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_u)\bigr)\bigr)}{\sum_{w \in N(v)}exp\bigl(LeakyRelu\bigl(\mathbf{a}^{(l+1)\top}Concat(\mathbf{W}^{(l+1)}_a h^{(l)}_v ; \mathbf{W}^{(l+1)}_a h^{(l)}_w)\bigr)\bigr)} \in \mathbb{R}$$
* ゲート付きグラフネットワークは、GRUという時系列処理で多少人気のあったニューラルネットワークの構造にむりやりメッセージ伝達をねじ込んだ構造をしている。
$$f^{集約}_{(l+1)}\bigl(h^{(l)}_v, \{\{h^{(l)}_u | u \in N(v)\}\}\bigr) = (1 - z^{(l+1)}_v)\odot h^{(l)}_v + z^{(l+1)}_v \odot \tilde{h}^{(l+1)}_v$$
$$\tilde{h}^{(l+1)}_v = tanh \bigl( \mathbf{W}m^{(l+1)}_v + \mathbf{U}\bigl(r^{(l+1)}_v \odot \tilde{h}^{(l+1)}_v\bigr)\bigr)$$
$$r^{(l+1)}_v = \sigma(\mathbf{W}^{(r)}m^{(l+1)}_v + \mathbf{U}^{(r)}h^{(l)}_v)$$
$$z^{(l+1)}_v = \sigma(\mathbf{W}^{(z)}m^{(l+1)}_v + \mathbf{U}^{(z)}h^{(l)}_v)$$
$$m^{(l+1)}_v = \sum_{u \in N(v)} h^{(l+1)}_u + b$$
※個人的にはGRUももう使わない。
* 異類選好型グラフにもグラフニューラルネットを使うぞ！という時には、
① 集約時に自身のノードに関する表現と、近傍集合から得られる表現を区別して集約する
② 集約時に$n$ホップ先までの情報を連結して保持しておく
③ 途中結果もどんどん使えるように、埋め込みを以下のように獲得しておく
$$\mathbf{Z} = Concat\bigl(\mathbf{H}^{(1)},\mathbf{H}^{(2)},....,\mathbf{H}^{(L)}\bigr)$$
という工夫をすれば良いらしい。
#### 後編へ続く
Sign in with Wallet
Connect another wallet