グラフラプラシアン
ある無向グラフの隣接行列$ Aの$ (i,j)要素を$ a_{ij}とする。次の関数を考える。
$ f({\bf x})=\frac{1}{2}\sum_{i,j}a_{ij}(x_i - x_j)^2
$ x_i...$ i番目のノードが保持する値。
初期値の与え方はいくつかの考え方がある。
この値を操作することによって目的関数の最小化を図る。類似したノードは似た値を持つようになる。
$ f ... $ n次元スカラ値関数
この関数を最小化することにより、関連性の高いノード$ x_iが近い値をとるように調整される。ノード$ iとノード$ jの関連性は隣接行列$ a_{ij}によって与えられる。
グラフラプラシアンは目的関数を整理することにより求められる。
$ f({\bf x}) = \frac{1}{2} \sum_{i,j} a_{ij}(x_i - x_j)^2
$ = {\bf x}^\top L {\bf x}
となる。ただし、$ L = D+Aである。
$ f... 目的関数（スカラ値）
$ L... グラフラプラシアン（正方行列）
$ D ... 次数行列（正方行列）
$ {\bf x} = (x_1, x_2, \ldots , x_n)^\top
グラフラプラシアンの性質
半正定値行列である
固有値は非負となる
導出過程
目的関数は$ f({\bf x})
$ f({\bf x}) = \frac{1}{2} \sum_{i,j} a_{ij}(x_i - x_j)^2
$ = \frac{1}{2}\sum_{ij}a_{ij}(x_i^2 - 2x_ix_j + x_j^2)
$ = \frac{1}{2}\left(\sum_{i, j}a_{ij}(x_i^2 + x_j^2) -2 \sum_{i,j}a_{ij}x_ix_j\right)
第１項目について考える。無向グラフの場合、隣接行列$ Aは対称行列となるので、$ a_{ij} = a_{ji}より
$ \sum_{i,j} a_{ij}x_{i}^2 = \sum_{i,j} a_{ij}x_j^2
また、
$ \sum_i \sum_j a_{ij} = \sum_{i} d_{ii}
とできる。ここで$ d_{ij}は$ i番目の対角要素に$ Aの$ i列（行）の和、それ以外は$ 0の値をもつ対角行列$ Dの$ (i,i)要素である。
$ d_{ij} = \begin{cases} \sum_{j}a_{ij}& i = j\\ 0& i \neq j\\ \end{cases}
よって、
$ \sum_{i, j} a_{ij}(x^2_i + x_j^2) = 2\sum_{i,j} d_{ii}x_i^2
$ =2{\bf x}^\top D {\bf x}
となる。
第２項目については
$ = 2\sum_{i, j} a_{ij}x_ix_j = 2{\bf x}^\top A {\bf x}
であるので、
$ f({\bf x}) ＝\frac{1}{2}\left( 2{\bf x}^\top D{\bf x} + 2{\bf x}^\top A {\bf x}\right)
$ = {\bf x}^\top D{\bf x} + {\bf x}^\top A {\bf x}
$ = {\bf x}^\top ( D+A) {\bf x} = {\bf x}^\top L {\bf x}