オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

トップ > データサイエンス > 【深層学習】Spectral Graph Convolution Network / Spectral GCN

【深層学習】Spectral Graph Convolution Network / Spectral GCN

データサイエンス データサイエンス-深層学習 データサイエンス-グラフ処理

Index

Spectral Graph Convolution Network / Spectral GCN

GCN における手法のひとつ.

信号処理の考えに基づいたもの.

信号処理では、信号を周波数領域へと変換することによって、 圧縮やノイズ除去などを効果的に行う.

フーリエ変換

信号処理では、音声などの波形をフーリエ変換によって周波数変換し、 その上で、ノイズ除去などをして逆変換をする.

変換の狙い

信号処理は、時間-周波数解析によって、周波数領域へと変換する.

変換することで、圧縮・伝送・保存等の処理に対して、効果的な理論や応用を与えている.

グラフラプラシアン / Graph Laplacian

時系列信号に対する処理であるフーリエ変換を、グラフに対して、適用することを考える.

グラフにおいて、フーリエ変換に相当する処理が、グラフラプラシアンである.



ある単純無向グラフ G\ =\ (V,\ E) の隣接行列 A を考える.

n\ \times\ n の隣接行列 A\ \in\ M(n,\ n)



次に、次数行列 D を考える.

グラフラプラシアン L^{'} を以下のように定義する.

L^{'}\ =\ D\ -\ A



正規化グラフラプラシアン

正規化グラフラプラシアン

L\ =\ I\ -\ D^{-\ \displaystyle \frac{1}{2}}\ A\ D^{-\ \displaystyle \frac{1}{2}}

利用場面

特異値分解

(正規化) グラフラプラシアン L の固有値を [tex: \lamdba{i}]、対応する固有ベクトルを [tex: u{i}] とする.

これらを利用して、以下のように表現する.

L\ =\ U\ \Lambda\ U^{T}




フーリエ変換との関連

各固有ベクトルに対するスペクトルを、時系列信号における周波数成分と対応づけると、 フーリエ変換における考え方がグラフに対しても適用できるようになる.

信号処理において、入力を周波数成分に変換したように、 グラフにおいても、グラフラプラシアンの固有ベクトルごとの成分に変換して、 その上で畳み込みなどの処理を行う.

グラフフーリエ変換

L の固有ベクトルから構成される行列 U を用いて、 グラフフーリエ変換を行う.

x\ \in\ R^{N} をノードの特徴ベクトルとする.

グラフフーリエ変換 F と、逆グラフフーリエ変換 F^{-1} を以下のように、定める.

F(x)\ =\ U^{T}\ x\ =\ \hat{x}

F^{-1}(\hat{x})\ =\ U\ \hat{x}
もしくは、 F^{-1}(\ F(x)\ )\ =\ U\ U^{T}\ x\ =\ x





すなわち、入力グラフ信号を、グラフラプラシアンの固有ベクトルが張る直行空間に射影する操作が、 グラフラプラシアン変換である.

グラフ畳み込み演算

グラフラプラシアン変換の出力結果に、畳み込み演算を行う.

グラフのノードの特徴ベクトルである入力グラフ信号を x\ \in\ R^{N} として、 フィルタ g_{\theta} でグラフ畳み込み演算 *_{G} を行うことを考える.



g_{\theta}\ *_{G}\ x



ここで、 \theta はパラメータ.

また、グラフ畳み込み演算は、スペクトル領域で行う畳み込み演算であるため、 g_{\theta} と x をグラフフーリエ変換することから始まり、 畳み込み演算 (要素積)を行い、また元の領域へ逆グラフフーリエ変換することを考える.

\begin{eqnarray} g_{\theta}\ *_{G}\ x\ &=&\ F^{-1}\ (F(g_{\theta})\ \bigodot\ F(x)) \\ \\ &=&\ F^{-1}\ (U^{T}\ g_{\theta}\ \bigodot\ U^{T}\ x) \\ \\ &=&\ U\ (U^{T}\ g_{\theta}\ \bigodot\ U^{T}\ x) \end{eqnarray}



フィルタ g_{\theta} のグラフフーリエ変換の結果である、グラフフーリエ係数 \Theta_{g} を以下のようにおく.



\Theta_{g}\ =\ U^{T}\ g_{\theta}



すると、

\begin{eqnarray} g_{\theta}\ *_{G}\ x\ &=&\ U\ (U^{T}\ g_{\theta}\ \bigodot\ U^{T}\ x) \\ \\ &=&\ U\ (\Theta_{g}\ \bigodot\ U^{T}\ x) \\ \\ &=&\ U\ (U^{T}\ x\ \bigodot\ \Theta_{g}) \\ \\ &=&\ (U\ diag(\Theta_{g})\ U^{T})\ x) \\ \end{eqnarray}



diag(\Theta_{g})\ =\ \Theta



とおくと、以下のようになる.

\begin{eqnarray} g_{\theta}\ *_{G}\ x\ &=&\ (U\ diag(\Theta_{g})\ U^{T})\ x) \\ \\ &=&\ U\ \Theta\ U^{T}\ x \\ \end{eqnarray}

畳み込み情報の工夫

diag(\Theta_{g}) は、 \Theta_{g} の値を対角成分にもつ対角行列である.



しかし、このようにして定義したフィルタはグラフ構造に依存せず、 畳み込みにおいて望ましい性質 (局所性など) を持っていない.

そこで、 \Theta_{g} を意味のある畳み込みにするために、 \Theta_{g} を グラフラプラシアンの固有値に基づいて表す.



具体的には、フィルタ g_{\theta} をグラフラプラシアンの固有値の N 次多項式 p_{N}(\Lambda) として定義する.



diag(\Theta_{g})\ =\ p_{N}(\Lambda)



これを、 p_{N}(\Lambda)\ =\ g_{\theta}(\Lambda) とおいても考える.



すると、グラフフーリエ変換した結果は、以下のようにかける.

\begin{eqnarray} g_{\theta}\ *_{G}\ x\ &=&\ (U\ diag(\Theta_{g})\ U^{T})\ x) \\ \\ &=&\ U\ p_{N}(\Lambda)\ U^{T}\ x \\ \end{eqnarray}

課題



1 つ目の課題は、ChebNet で、2 つ目の課題は、Spatial GCN で対応する.



応用アルゴリズム

ChebNet / 2016

上の 1 つ目の課題における対応策.

フィルタ g_{\theta}(\Lambda) を k 次までのチェビシェフ多項式を用いて、近似する.

  • Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

GCN (Kipf & Welling) / 2016

GCN の代表的な手法で、GCN と称される.

参考

書籍

Web サイト