GCN

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

過去回

第1回:Graph, GNN


グラフの畳み込み

画像の畳み込み

畳み込みとは数学的な操作である。参考URL

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

フーリエ変換とは?

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

画像のフーリエ変換

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

フーリエ変換と畳み込みの性質して次のような式が成り立つ(* は畳み込み)
関数

fに対する関数
g
の畳み込み操作は、それぞれをフーリエ変換した関数同士の要素積を再度逆フーリエ変換したものとして表すことができる。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


GNNの発展

Spectral based な手法と、Spectral based の手法がある。
Spectral based はグラフフーリエ変換して畳み込みをする話。spartial based は直感的な手法(前回の発想

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

今回はSpectral based のGNNの話


Spectral based GNN

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

拡散方程式の右辺

2/x2はラプラシアンと呼ばれる作用素である。

同様に、グラフにおけるノードの値の時間発展を考える。
次のように

Lの行列を定義すると
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

tx(t)=κLx(t)

式を見比べると、

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

補足

グラフは、ある瞬間においてリンクのあるノード間で情報のやり取りが行われると想定できる。
その想定において、この行列は、ある時間

tにおける情報量の変化を記述しているとみなせる。
例えば、各ノードが
t1
(1,2,3,4)
という情報量を持っている場合、
(2110131111310112)(1234)=(+223+01+23412+94+023+8)=(3623)

(3,6,2,3)
という情報量の変化が発生する。
という風に、グラフのノードが、ノード同士で情報のやり取りを行っていると想定すると、そのやり取りはラプラシアン行列で記述できる。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

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

F(x)について考える。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

上記の式は、隣り合うノードの振動の滑らかさ(もしくは激しさ)を表す指標である。
これの

|x|=1という条件のもとでの停留値
λ
(つまり微分=0)について考えると、

Lx=λx

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

F(x)の停留値となる。

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

考え方の流れのおさらい

フーリエ変換は振動数への変換である

グラフにおける振動を定義する(ノード間の値の差の二乗)

グラフの振動の停留値について解くと(つまり振動数空間への変換を試みる操作に置き換えれる?)、グラフラプラシアンの固有関数への展開とみなせる

グラフラプラシアンの固有値は、グラフの振動におけるフーリエ変換後の振動数を示しており、つまり固有関数はフーリエ変換の操作と定義できる

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

グラフ畳み込みの一般化

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

結局、N個先の隣接ノードまでの情報量を計算する際のラプラシアンは、

LNと定義できる。
同様にそのラプラシアンの固有ベクトルの展開は、二乗を例とすると

L2=LL=UΛUTUΛUT=UΛIΛUT=UΛ2UT

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

y=UΛUTx+UΛ2UTx+...+UΛNUTx=U(k=1NΛk)UTx=Ugθ(Λ)UTx

のように、結局、

LNまでを考慮した形も同じように記述できる。


ChebNet

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

下記の式について、固有ベクトル

Uを計算するのは計算コストが高いためしたくない。

y=Ugθ(Λ)UTx

なので、固有ベクトルを無くしたい。そこで、

Ugθ(Λ)UT の部分というのは、
L
に関連する何かだよね、と仮定できるので、次のように変形する。
y=Ugθ(Λ)UTx=gθ(L)x

(個人的には思い切りのある変換だと思うが)これで、式から

Uが消えたので、固有ベクトルを計算しなくてよくなる。計算前のグラフラプラシアンを使えば良い。

そこで、

gθ(L)を次のように定義する。

gθ(L)=k=0KθkLk

この

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

(以下をなぜしているのか不明。多分計算が簡単になる?)

チェビシェフ多項式を使って、

gθを展開する。

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


GCN

ChebNet はK近傍までのノードについて畳み込んでいる。
GCNは、もう

K=1までで良くない? と簡略化したもの。

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