はじめに

Spectral Networks and Deep Locally Connected Networks on Graphsを読んだのでメモ．前回spectral clusteringの勉強の中でgraph Laplacianについて触れたので，せっかくだから今一度いわゆるgraph convolution関連の論文を読み漁ろうかなと．この論文は2013年の論文で，サーベイ不足でなければ世間で言われているgraph convolutionをちゃんと定式化した最初の論文．

CNNとgraph

Convolutional Neural Networks (CNNs)は基本的にregular grid上のデータ(画像や動画など)を処理する上で優れた性能を発揮している．特に，そのregular gridの構造をうまく使うことでパラメータ数の大きな削減ができていることがポイント．具体的には以下の3つがCNNの重要な点．

The translation structure (一般的な線形写像の代わりにfilterを使うことによるweight sharing)
The metric on the grid (入力信号に比べて非常に小さいサイズのフィルタの適用)
The multi scale dyadic clustering of the grid (strideが2以上のconvolutionやpoolingによるsubsampling)

ただし，CNNはregular gridでない，一般的なgraph構造を持つデータには適用できない．そこでここではCNNの拡張として2つの構造を提案する．最初に2.と3.を一般のgraphに拡張したSpatial Constructionを導入し，次にFourier domainにおける畳み込みを使うSpectal Constructionを導入する．

Spatial Construction

入力データとして重み付きグラフ $G=(\Omega, W)$ を考える． $\Omega$ はサイズ $m$ の離散集合でグラフの頂点を表現するもの． $W$ は $m\times m$ の要素が非負の対象行列でいわゆる重み付きの隣接行列．

$W$ における局所性

局所性(隣接関係)はグラフにおいて簡単に一般化が可能．例えば， $W$ における隣接の定義はある閾値 $\delta\gt 0$ を超えるものとして以下のように記述可能．

$\displaystyle N_\delta(j)=\{i\in\Omega :W_{ij}\gt\delta\}$

この定義によって与えられる隣接関係を使えば，局所的な接続のみを見ることでCNNと同様にパラメータ数を減らすことができる，

グラフ上でのMultiresolution

CNNで使われるpooling等によるsubsampling layerはgridのmultiscale clusteringとして考えることが可能．multiscael clusteringはクラスタに含まれる全ての頂点の持つ特徴量を入力として，クラスタの代表値として一つの特徴量を出力する関数として考えることができる．クラスタリングのためのクラスタはgraph Laplacianの文脈で様々な研究がされているためここではあまり深入りせず，naive agglomerative methodを使ってクラスタを決めるとのこと．このクラスタリングのクラスタ数によってグラフの解像度が決定する．

Deep locally connected networks

グラフにおける局所性と解像度が定義できたので一般化されたネットワークを導入する．まずネットワークによる計算の前にグラフのmultiscale clusteringから始める．ここでは $K$ 個のスケールを考える．入力として $\Omega_0=\Omega$ を定義し，各スケール $k=1,\dots,K$ におけるグラフのクラスタリング結果を $\Omega_k$ とする．ただし， $\Omega_k$ は $\Omega_{k-1}$ を $d_k$ 個のクラスタに分けた結果．さらに， $k$ における隣接関係は次のように与えられる．

$\displaystyle \mathcal{N}_k=\{\mathcal{N}_{k,i};i=1,\dots,d_{k-1}\}$

以上を使って，ネットワークの第 $k$ 層を定義する。入力は $\Omega_0$ で定義される実数の信号とし， $f_k$ を第 $k$ 層のフィルタの数とする．ネットワークの第 $k$ 層は $\Omega_{k-1}$ で記述される $f_{k-1}$ 次元の信号を $\Omega_k$ で記述される $f_k$ 次元の信号へと変換する．

より一般的に， $k$ 層目の入力を $x_k\in\mathbb{R}^{d_{k-1}\times f_{k-1}}$ とすればその出力 $x_{k+1}$ は次のように記述される．

$\displaystyle x_{k+1,j}=L_kh\left(\sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i}\right)\:\:(j=1,\dots,f_k)$

$F_{k,i,j}\in\mathbb{R}^{d_{k-1}\times d_{k-1}}$ は隣接関係 $\mathcal{N}_k$ に従って定義されるスパースな行列． $L_k$ は出力を $\Omega_k$ に従ってクラスタリングするプーリングの操作を表す．

論文の文章を無視して簡単にまとめると，上の式の $i,j$ はそれぞれCNNでいう入力のチャネルと出力のチャネルを表していて， $F_{k,i,j}$ は隣接関係があるとこのみ値を持つ $d_{k-1}\times d_{k-1}$ 行列，すなわち $F_k$ 自体は $F_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}$ になる．また $x_{k.i}\in\mathbb{R}^{d_{k-1}}$ から $F_{k,i,j}x_{k,i}$ は行列とベクトルの積になっていて，要は隣接関係のあるノードにだけ重みをかけて総和を取る処理になっている．それに加えて $\sum_{i=1}^{f_{k-1}}$ でチャネルでの総和を取っているため，CNNと同一の処理（空間方向，チャネル方向に重みをかけて総和）になっていることがわかる．

ここでは隣接関係 $\mathcal{N}_k$ は次の手順によって得られる．

$\displaystyle W_0=W \\ \displaystyle A_k(i,j)=\sum_{s\in\Omega_k(i)}\sum_{t\in\Omega_k(j)}W_{k-1}(s,t),\:(k\leq K) \\ \displaystyle W_k=\mathrm{rownormalize}(A_k),\:(k\leq K) \\ \displaystyle \mathcal{N}_k=\mathrm{supp}(W_k),\:(k\leq K)$

またクラスタリング結果 $\Omega_k$ はここでは $\epsilon$ coveringで与える． $\epsilon$ coveringは類似度カーネル $K$ (ガウスカーネル等)とグラフの分割結果 $\mathcal{P}=\{\mathcal{P}_1,\dots,\mathcal{P}_n\}$ を使って $\sup_n\sup_{x,x'\in\mathcal{P}_n}K(x,x')\geq\epsilon$ として分割を与える方法で，簡単にいってしまえば以前のspectral clusteringの勉強でやったfully connected graphに閾値を設けてグラフを分割するという感じ．

ここで $S_k$ を各ノードの隣接ノード数の平均とすれば， $k$ 層における学習パラメータのオーダーは $\mathcal{O}(S_k\cdot|\Omega_k|\cdot f_k\cdot f_{k-1})$ となる．

ただ，論文にも書いてあるよう，隣接関係はデータごとに違うためweight shareの構造を導入するのは容易ではなく，単純に実装してしまえば $F_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}$ を学習パラメータとして持つことになる．一応グラフ全体を低次元空間に埋め込むというのが回避策として書かれているが，この論文で考えているようなデータではそこまで高次元のものはほとんど出てこないからおっけー的なことも主張している．

Spectral Construction

今度はgraph Laplacianの固有値を使った畳み込みの一般化を考える．

重み付きグラフ上での調和解析

ここではgraph Laplacianの呼び方は前回の勉強のメモに合わせて， $L-D-W$ をunnormalized Laplacian， $\mathcal{L}=I-D^{-1/2}WD^{-1/2}$ をnormalized Laplacianとする（論文ではそれぞれcombinatorial Laplacian，graph Laplacianと定義している）．ここではシンプルにunnormalized Laplacianを使う．仮に信号 $x$ を $m$ 次元のベクトルとすれば，ノード $i$ における信号の変化の滑らかさ $||\nabla x||^2_W$ (グラフにおける周波数)は次のように定義できる．

$\displaystyle ||\nabla x||^2_W(i)=\sum_jW_{ij}[x(i)-x(j)]^2$

さらに全体としては

$\displaystyle ||\nabla x||^2_W=\sum_i\sum_jW_{ij}[x(i)-x(j)]^2$

となる．上記の定義に従えば最も滑らかなベクトルは常に

$\displaystyle v_0=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1}||\nabla x||^2_W=(1/\sqrt{m})1_m$

となり，続く値

$\displaystyle v_i=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1,x\perp\{v_0,\dots,v_{i-1}\}}||\nabla x||^2_W$

は $L$ の固有ベクトルで与えられる．最小化問題の解 $v_i$ が $L$ の固有ベクトルから得られるのは $2x'Lx=\sum_i\sum_jW_{ij}[x(i)-x(j)]$ の関係からわかる．この関係の証明は前の記事参照．各固有ベクトルに対応する固有値 $\lambda_i$ jはgridに定義された信号のフーリエ係数として見ることができ，同様に固有ベクトルはフーリエ基底として考えられる．直感的なところではグラフにおける周波数 $||\nabla x||^2_W$ のargminがgraph Laplacianの固有ベクトルから与えられることと，固有値と固有ベクトルの関係から $Lx=\lambda x$ の関係が成り立つ，すなわちグラフの構造を表す $L$ が固有ベクトル（フーリエ基底）とその固有値による線形結合で与えられることからフーリエ変換としてみなせるというもの？（グラフ信号処理ど素人の自分なりの解釈なので自信はない）

以上を踏まえれば信号の変換はフーリエ基底の結合係数を変化させることと考えられる，すなわち固有ベクトルとdiagonalな行列の積として考えられるためパラメータ数は $\mathcal{O}(m^2)$ から $\mathcal{O}(m)$ として表現できる．

Extending convolutions

ここまでの関係を使って，ネットワークの定義を行う． $V$ をgraph Laplacianの固有ベクトルとする．すると第 $k=1,\dots,K$ 層における入力 $x_k\in\mathbb{R}^{|\Omega|\times f_{k-1}}$ に対する変換はsubsamplingを考えなければ次のようにかける．

$\displaystyle x_{k+1,j}=h\left(V\sum_{i=1}^{f_{k-1}}F_{k,i,j}V^Tx_{k,i}\right)\:\:(j=1,\dots,f_k)$

$F_{k,i,j}$ は対角行列で， $h$ は非線形関数を表す．実験的に，graph Laplacianの最初の $d$ 個の固有ベクトルを使う場合の方がいい場合があるらしい（つまりは高周波成分は無視するということ）．仮に $d$ 個の固有ベクトルを使ったとすれば，学習パラメータのオーダーは $\mathcal{O}(f_{k-1}\cdot f_k\cdot d)$ になる．ただし，計算コストの面においては $V$ と $V^T$ の積があるため非常に大きくなっていることには注意（加えてgraph Laplacianの固有ベクトルを求める必要もある）．