はじめに

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKSを読んだのでメモ．

Fast approximate convolutions on graphs

ここでは次のような多層のgraph convolutional networks（GCN）を考える．

$\displaystyle H^{(l+1)}=\sigma\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)}\right)$

$\tilde{A}=A+I_N$ は無向グラフ $\mathcal{g}$ に自己ループを加えた隣接行列を表し， $\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}$ と $W^{(l)}$ は学習パラメータ． $\sigma(\cdot)$ はReLUなどの活性化関数で， $H^{(l)}\in\mathbb{R}^{N\times D}$ は $l$ 層目の出力．

Spectral graph convolution

グラフフーリエ変換によるグラフ上でのフィルタリングは次のような入力信号 $x\in\mathbb{R}^N$ と $\theta$ をパラメータとするフィルタ $g_\theta=\mathrm{diag}(\theta)$ の積によって表現される．

$\displaystyle Ug_\theta U^{T}x$

ここで $U$ はnormalized graph Laplacian $L=I_N-D^{-1/2}AD^{-1/2}=U\Lambda U^T$ の固有ベクトルで， $\Lambda$ は固有値を対角成分とする対角行列．ここで $g_\theta$ は固有値の関数 $g_\theta(\Lambda)$ と見ることができる．ここでの問題として，固有ベクトル行列 $U$ の行列積が $\mathcal{O}(N^)$ となり計算コストが高いことと，グラフラプラシアンの固有値分解の計算が巨大なグラフに対しては現実的でないことがあげられる．ここでは次のような $k$ 次のチェビシェフ多項式による近似を使ってこの問題を回避する．

$\displaystyle g_{\theta'}(\Lambda)\approx\sum_{k=0}^K\theta_k'T_k(\tilde{\Lambda})$

ただし， $\tilde{\Lambda}=\frac{2}{\lambda_{\mathrm{max}}}\Lambda-I_N$ で $\lambda_{\mathrm{max}}$ は $L$ の最大固有値．また， $\theta'\in\mathbb{R}^L$ はチェビシェフ係数．チェビシェフ多項式は $T_k(x)=2xT_{k-1}(x)-T_{k-2}(x),\:T_0(x)=1,\:T_1(x)=x$ として再帰的に計算される．

畳み込みの話に戻れば，近似を使った畳み込みの計算は以下のように定義される．

$\displaystyle Ug_\theta U^{T}x\approx\sum_{k=0}^K\theta_k'T_k(\tilde{L})x$

ただし， $\tilde{L}=\frac{2}{\lambda_{max}}L-I_N$ ．重要なのはチェビシェフ多項式の次数 $K$ がフィルタサイズと対応している．ここまでは前回読んだ論文の内容．

Layer-wise linear model

この論文ではチェビシェフの多項式で近似されたモデルに対し $K=1$ の場合のみについて考える．この場合モデルはグラフラプラシアンに関して線形になっている．そのためモデルの表現力は大きく下がるが，そこはNNの多層構造によって補う．むしろ $K=1$ とすることで，過学習を抑制する効果が期待できる．

以降，計算を簡単にするため $\lambda_{\max}\approx 2$ として扱う．この近似のもとではgraph convの計算式は以下のようになる．

$\displaystyle \theta_0'x+\theta_1'(L-I_N)x=\theta_0'x+\theta_1'D^{-1/2}AD^{-1/2}x$

これは $\theta_1,\theta_2$ という二つの学習パラメータを持つ．そこで，過学習を抑制するためのさらなるパラメータ数の制限として以下のような表現を用いる．

$\displaystyle \theta\left(I_N+D^{-1/2}AD^{-1/2}\right)x$

ここでは一つのパラメータ $\theta=\theta_0'=-\theta_1'$ のみを持つ．こんなんありかという感じだがまあ実験的にはいいんでしょう．グラフ上でのフィルタリング処理は元々はグラフ信号処理で研究されていたものなので，deep neural netに適用した際に勾配消失や爆発に関する問題を避けるような工夫はない．そこでさらなるテクニック(論文中でrenormalization trickと呼ばれていた)として， $I_N+D^{-1/2}AD^{-1/2}\rightarrow \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ という変換を行う．ただし， $\tilde{A}=A+I_N,\:\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}$ ．これにより勾配の消失，爆発を抑制できるらしい（よくわからない）．

ここまでの定義を，入力信号 $X\in\mathbb{R}^{N\times C}$ ( $C$ は入力のチャネル数)に対して一般化すると次のようにかける．

$\displaystyle Z=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X\Theta$

$\Theta\in\mathbb{R}^{C\times F}$ は学習パラメータで， $Z\in\mathbb{R}^{N\times F}$ は出力．計算オーダーとしては $\mathcal{O}(|\mathcal{E}|FC)$ となり， $\tilde{A}X$ は疎な行列と密な行列の積として実装可能．

Semi-supervised node classification

今まで頑張って定義したGCNを使ってsemi-supervised learningをしようというもの．基本的には最終層にsoftmax関数をかけて得た出力 $Z$ と，正解ラベル $Y$ を使って次のcross-entropyを最小化するよう学習する．

$\displaystyle L=-\sum_{l\in\mathcal{Y}_L}\sum_{f=1}^FY_{lf}\mathrm{ln}Z_{lf}$

$\mathcal{Y}_L$ はラベルを持つ各ノードの集合．要はラベルがあるノードだけを使って分類問題を学習するという単純なもの．ただし，この論文ではSGDではなくbatch gradient descentで学習したとのこと．ただし，確率要素を加えるためdropoutを使ったらしい．dropout使うならデータをサンプリングしてSGDでやってもいい気はするけどどうなんでしょうという気持ち．

まとめ

Renormalizationのあたりがよくわからなかったが実験的にはrenormした方が精度が上がっていた．renormしないほうがresnetの残差学習の形になっていていい気がするんだけどよくわからん．でもこの論文の実験結果からもパラメータ2つより1つにした方が精度上がってたから，前の論文でチェビシェフ使った近似の方が精度良くなってたのはやっぱりパラメータ数が減ったからなのか．

後，ひとつ面白かったのはAppendixのBの実験で，2,3層くらいの浅いモデルが一番汎化して精度がよかったこと．データセットの問題かグラフデータの性質かモデルが悪いのかわからないけどGCNでdeepなモデルを学習するのはひとつの課題っぽい．