はじめに

Learning Laplacian Matrix in Smooth Graph Signal Representationsを読んだのでメモ．

気持ち

データの構造をグラフで表現する際に，一般的にはgeographicalもしくはsocial friendshipなどに基づいてグラフ構造を決定する．ただこのような決め方は常に良い方法とは言えない，またはこのようなグラフ構造の導入が常にできるとは限らない．なので観測されたデータから学習ベースでグラフ構造を決めようというのがこの論文のゴール．ただしデータサンプルからグラフ構造の決定は基本的にはill-posed problemなのでグラフの滑らかさを使ってうまく扱う方法を提案．

Smooth graph signals

まず滑らかなグラフとは何かというところから．ここではノード数 $n$ の重み付き無向グラフ $G=\{V,E,\omega\}$ を考える． $V,E,\omega$ はそれぞれグラフのノードとエッジとエッジが持つ正の重みを表す． $W$ を重み付き隣接行列， $D$ を度数行列とすれば非正規化グラフラプラシアン $L$ は次のように表現できる．

$\displaystyle L=D-W$

$L$ は固有値分解可能なため固有値 $\Lambda$ 固有ベクトル $\chi$ を使って次のように表現できる．

$\displaystyle L=\chi\Lambda\chi^T$

また， $L$ の最小固有値は0でその個数はグラフのconnected componentsの数に一致する．

ここでグラフ $G$ 上のグラフ信号 $f$ のsmoothnessは次の2次形式で測ることができる．

$\displaystyle f^TLf=\frac{1}{2}\sum_{i\sim j}w_{ij}(f(i)-f(j))^2$

$w_{ij}$ は頂点 $i,j$ を結ぶエッジの重みで $f(i),f(j)$ は各頂点の信号の値．つまりエッジの重みを使って重みづけられたノード間の信号の変化分の大きさが小さいほどグラフは滑らかであるということ．

グラフラプラシアンの細かい話は以前勉強したメモがあるのでそちらを参照．

Representation via factor analysis model

ここでは因子分析に基づくsmooth graph signalsのための表現モデルを提案する．factor analysis modelは線形モデルの一種で，今回は次のモデルを考える．

$\displaystyle x=\chi h+u_x+\epsilon$

$x\in\mathbb{R}^n$ は観測されたグラフ信号の表現で， $h\in\mathbb{R}^n$ は潜在変数で固有ベクトル行列 $chi$ を通して $x$ をコントロールする． $u_x\in\mathbb{R}^n$ は $x$ の平均．ここでは雑音 $\epsilon$ は等方性であるとし，平均0，分散 $\sigma^2_\epsilon I_n$ の多変量ガウス分布を仮定する．よって $\epsilon$ の確率密度関数は次のようになる．

$\displaystyle \epsilon\sim\mathcal{N}(0,\sigma^2_\epsilon I_n)$

今回のモデルは一般的な因子分析モデルのグラフ信号への一般化になっていて，重要となるのは $L$ の固有ベクトル $\chi$ で表現される表現行列の選択．選び方には二つの観点があって，一つはグラフのトポロジーを反映したものを探すことで，もう一つは表現行列がグラフのフーリエ基底として解釈可能であるということ．なので $L$ の固有ベクトルは表現行列の良い候補になる．

今回はクラシカルな因子分析モデルに従って潜在変数をガウシアンと仮定．もっと言えばここではガウシアンを平均0，精度行列を $L$ の固有値 $\Lambda$ とする以下の形で定義する．

$\displaystyle h\sim \mathcal{N}(0,\Lambda^\dagger)$

$\Lambda^\dagger$ は $\Lambda$ のムーアペンローズの擬似逆行列． $L$ の固有値はグラフの周波数を表しているため，低周波ほどエネルギーを持つということを暗に仮定していること．今までの関係を用いれば $x$ の条件付き確率と $x$ の確率は次のように表現可能．

$\displaystyle x|h\sim\mathcal{N}(\chi h+u_x,\sigma^2_\epsilon I_n) \\ \displaystyle x\sim\mathcal{N}(u_x,L^\dagger+\sigma^2_\epsilon I_n)$

ただし $L^\dagger=\chi\Lambda^\dagger\chi^T$ の関係を満たす．

Learning framework

観測 $x$ と $h$ の事前分布が与えられたとし， $h$ のMAP推定を行う．すると $h$ のMAP推定は次のように表される．

$\displaystyle h_{MAP}(x):=\mathrm{argmax}_hp(h|x)=\mathrm{argmax}_hp(x|h)p(h)=\mathrm{argmin}_h(-\log p_E(x-\chi h)-\log p_H(h))$

$p_E(\epsilon)=p_E(x-\chi h),p_H(h)$ は雑音と潜在変数の確率密度関数を表し， $p(h|x)$ は $x$ が与えられた時の $h$ の条件付き確率密度関数．ここでそれぞれガウス分布を仮定すれば次のように書き直せる．

$\displaystyle h_{MAP}(x):=\mathrm{argmin}_h(-\log p_E(x-\chi h)-\log p_H(h))\\=\mathrm{argmin}_h(-\log e^{-(x-\chi h)^T(x-\chi h)}-\alpha\log e^{-h^T\Lambda h})=\mathrm{argmin}_h|x-\chi h|^2_2+\alpha h^T\Lambda h$

$\alpha$ は定数でノイズの無い状況においては解は $x=\chi h$ ．また $\chi$ は直交行列なので $x=\chi h$ において $h=\chi^Tx$ が成り立つので以下の最小化問題へと書き直せる．

$\displaystyle h^T\Lambda h=(\chi^Tx)^T\Lambda\chi^Tx=x^T\chi\Lambda\chi^Tx=x^TLx$

すなわち $L$ の特性からこの最小化問題はグラフの信号 $x$ が滑らかになるような解を導く．

ここでグラフ構造は未知であるためこの最小化問題は潜在変数 $h$ と表現行列 $\chi$ と $h$ の事前分布に対する精度行列 $\Lambda$ を変数に持つ．すなわち次の最小化問題として表される．

$\displaystyle \min_{\chi,\Lambda,h}|x-\chi h|_2^2+\alpha h^T\Lambda h$

さらに $y=\chi h$ という変数変換を用いれば次のようにかける．

$\displaystyle \min_{L,y}|x-y|_2^2+\alpha y^TLy$

Learning algorithm

最終的に得られた最小化問題を行列形式で書き直すと次のようになる．

$\displaystyle \min_{L\in\mathbb{R}^{n\times n},Y\in\mathbb{R}^{n\times p}}|X-Y|^2_F+\alpha\mathrm{tr}(Y^TLY)+\beta|L|^2_F,\\ \mathrm{s.t.}\:\mathrm{tr}(L)=n,\:L_{ij}=L_{ji}\leq 0,\:i\neq j,\:L\cdot\mathbf{1}=\mathbf{0}$

$X\in\mathbb{R}^{n\times p}$ は $p$ 個のデータを並べたもので， $\alpha,\beta$ は正の正則化パラメータ．この論文ではこの最小化問題を $L$ と $Y$ の交互最適化によって解く．

$\displaystyle \min_L\alpha\mathrm{tr}(Y^TLY)+\beta|L|_F^2\\ \mathrm{s.t.}\:\mathrm{tr}(L)=n,\:L_{ij}=L_{ji}\leq 0,\:i\neq j,\:L\cdot\mathbb{1}=\mathbb{0}$