目的
グラフニューラルネットワークの論文を読んでいると突然
グラフフーリエ変換後のフィルタリングを1次の項までで近似すると以下の式が導出できる. ここの$\theta_0$と$\theta_1$と$\vec{\beta}$を学習させる.
$$P^{T}(\theta_0I+\theta_1\Lambda) P\vec{x}+\vec{\beta}$$
ここで$\Lambda$はラプラシアン行列の固有値行列で, $P$がラプラシアン行列の対角化行列である.
などといった文章が出てくることがある.
これについて信号処理の知識で導出している文書は多いものの, 恥ずかしながら筆者は信号処理に明るくないためよく理解できなかった.
そのため, 筆者と馴染みのある物理学の知識を用いて上式の導出を行う.
(そういった背景なので, いい加減なことを言っていたら訂正してくれるとありがたいです)
導出
出力$\vec{F}$が入力${x}$によって決定するものとする.
ここで, $\vec{F}$, $\vec{x}$は$d$次元のベクトルであり,$d$個の各ノードの出力入力に対応する.
$F_i$は$i$とその隣接ノード$\mathcal{N}_i$の入力からのみ影響をうけるとする.
この入力と出力は何でもいいが, 今回は$\vec{x}$が変位で$\vec{F}$が力の調和振動子モデルという見立てで話をすすめる.
入力値$\vec{x}$と出力値$\vec{F}$の関係は冪で展開すると$$
F_i(x)=\beta_i+\sum_{j\in \mathcal{N_i}} k_{ij}^{(1)}x_j+\sum_{j,k\in \mathcal{N_i}} k_{ijk}^{(2)}x_jx_k+\cdots
$$
と記述できる.
ここで2次項以降が無視できるとすると
$$
F_i(x)=\beta_i+\sum_j k_{ij}x_j =\beta_i+k_i^{\mathrm{self}}x_i+\sum_j k_{ij}^{\mathrm{int}}(x_j-x_i)
$$
となる.
ここで第2項が非相互作用項であり, 第3項が相互作用項である.
加えて, 各種ノードから受ける影響が対象的であると仮定する.
$$非相互作用項=F_i^{\mathrm{self}}(x)=k^{\rm{self}}x_i$$
$$ 相互作用項=F_i^{\mathrm{int}}(x)=k^{\mathrm{int}} \sum_{j\in \mathcal{N_i}} (x_j-x_i) $$
相互作用項について
相互作用項$\vec{F}_i^{\mathrm{int}}(x)$を行列表記する.
F_i^{\mathrm{int}}(x)=k^{\mathrm{int}} \sum_{j\in \mathcal{N_i}} (x_j-x_i)=k^{\mathrm{int}} \sum_jL_{ij}x_j \\
\vec{F}^{\mathrm{int}}(x)=k^{\mathrm{int}} L\vec{x}
ここで, 行列$L$はラプラシアン行列と呼ばれ
L_{ij}=\begin{cases}
-\# \mathcal{N}_i&(i=j)\\
1 &(j\in \mathcal{N}_i)\\
0 & \mathrm{otherwise}
\end{cases}
を満たす.
ラプラシアン行列$L$の対角化が$P^T\Lambda P$とすると
$$\vec{F}^{\mathrm{int}}(x)=k^{\mathrm{int}}P^T\Lambda P\vec{x}$$
非相互作用項について
非相互作用項$\vec{F}_i^{\mathrm{self}}(x)$も同様に行列表記する.
\vec{F}^{\mathrm{self}}(x)=k^{\mathrm{self}}\vec{x}=k^{\mathrm{self}}P^TP\vec{x}
ここで, 対角化行列$P$のエルミート性($P^TP=I$)を用いた.
まとめ
以上の式をふまえると
\vec{F}({x})
=P^{T}(k^\mathrm{self}I+k^\mathrm{int}\Lambda ) P\vec{x}+\vec{\beta}
が導出できる.
ここで, 未知の変数は$k^\mathrm{self}$, $k^\mathrm{int}$, $\vec{\beta}$の計$d+2$次元に抑えられる.
一方, 入力と出力が線形しか仮定しないとき(ニューラルネットにおける全結合層)の自由度は
\vec{F}=W\vec{x}+\vec{\beta}
なので$d^2+d$である.
よってグラフフーリエ変換とは, ｢エッジ(=最近接)での相互作用に対象性がある｣｢エッジ(=最近接)以外相互作用しない｣を仮定することで関数の自由度を下げるテクニックと解釈できる.
[おまけ]グラフフーリエ変換はどこがフーリエ変換っぽいのか
$\vec{F}$を力だとする.
$\vec{\beta}=0$のときの系の時間発展は$\vec{F}=m\partial_t^2\vec{x}$より
\vec{\omega}=\frac{k^{\mathrm{self}}}{m}\vec{1}+\frac{k^{\mathrm{int}}}{m}\vec{\lambda}
\\
\frac{\partial}{\partial t^2}P\vec{x}=(\mathrm{diag}{\vec{\omega}})P\vec{x}
上は波動方程式なので$\vec{\omega}$の三角関数の線形結合が$x$の解になる.
x_j=\sum_i A_{ij}\sin(\omega_j t+\theta_{ij})
よって, グラフフーリエ変換を行うことで入力の時間発展を各周波数成分に分解することができる.
[おまけ]ラプラシアン行列はどこがラプラシアンっぽいのか
流体力学などの空間をメッシュで区切るような数値計算を考える.
一次元の場合のラプラシアンは単純差分で計算すると
$$\nabla^2 f(x)\simeq f(x-1)+f(x+1)-2f(x)$$
であり, 2次元の場合は
$$\nabla^2 f(x)\simeq f(x-1,y)+f(x-1,y)+f(x,y-1)+f(x,y+1)-4f(x,y)$$
であるように, $\sum$(隣接するもの)-(隣接数)×自身をしている.
これをグラフに適用させた場合, ラプラシアン行列になる.