スペクトラルクラスタリング
離散グラフのグラフラプラシアンを用いて、ノードのクラスタリングを行うアルゴリズムのこと。
2. グラフラプラシアンの固有値問題を解く。
3. 最も小さい固有値を求めると、それに対応する固有ベクトルが目的関数$ fを最小化するノードの重みベクトル$ {\bf x}となる。
4. ベクトル$ {\bf x}の値に対してクラスタリングする。
ーーーー
ノードベクトル（？）に関する制約のもとでグラフラプラシアン（目的関数）の最小化問題をラグランジュの未定乗数法を用いて解く。
グラフラプラシアンの固有値問題に帰着され、その固有値が目的関数値を表す。
最小の固有値に対応する固有ベクトルが、解$ {\bf x}^*となる。
目的関数の最小化問題を考える。$ {\bf x}に何の制約も無ければ目的関数$ fはどれだけでも小さくできるので、それを避けるために制約条件
$ {\bf x}^\top {\bf x} = 1
を設定する。これを次の式で表す。
$ g({\bf x}) = {\bf x}^\top{\bf x} - 1
目的関数は
$ f({\bf x}) = {\bf x}^\top L{\bf x}
$ h({\bf x}, \lambda) = f({\bf x}) - \lambda g({\bf x})
$ = {\bf x}^\top L{\bf x} - \lambda ({\bf x}^\top{\bf x} - 1)
となり、
$ \frac{\partial h}{\partial {\bf x}} = 2 L{\bf x} - 2\lambda{\bf x} = {\bf 0}
$ L {\bf x} = \lambda {\bf x}
これはグラフラプラシアン$ Lについての固有値問題である。
左から$ \bf x^\topを掛けると、
$ {\bf x}^\top L{\bf x} = \lambda {\bf x}^\top{\bf x}
$ f({\bf x}) = \lambda
であるので、グラフラプラシアンの固有値は目的関数の値に対応していることがわかる。