グラフラプラシアン
定義
グラフ $G$の次数行列を$D$、[隣接行列](../1499）を$A$とする。このとき、$G$のグラフラプラシアンgraph Laplacian $L$は次のように定義される。
$$ L := D - A $$
説明
ユークリッド空間上の関数に対して定義されるラプラシアン $\Delta = \sum\limits_{i} \frac{\partial^{2}}{\partial x_{i}^{2}}$とは異なり、与えられるグラフに依存する。
グラフ $G = (V, E)$に対して $f : V \to \mathbb{R}$をノードシグナルとし、$\mathbf{f} = \begin{bmatrix} f(v_{1}) & \cdots & f(v_{n}) \end{bmatrix}^{\mathsf{T}}$のように表記しよう。すると、$L\mathbf{f}$の各成分は各頂点vertexにおける値が隣接する頂点の値とどれだけ差があるかを示している。
導出
多変数関数 $g : \mathbb{R}^{n} \to \mathbb{R}$に対してラプラシアンは次のように定義される。
$$ \nabla^{2} g = \Delta g = \dfrac{\partial^{2} g}{\partial x_{1}^{2}} + \cdots + \dfrac{\partial^{2} g}{\partial x_{n}^{2}} $$
実数空間上で定義された関数 $f : \mathbb{R} \to \mathbb{R}$の微分係数は次のように数値的に近似できる。
$$ f^{\prime}(x) = \dfrac{f(x+h) - f(x)}{h} $$
$$ f^{\prime \prime}(x) = \dfrac{f(x+h) - 2f(x) + f(x-h)}{h^{2}} \tag{1} $$
この式をグラフに対して考えてみよう。$x$を頂点と見なすと、$x+h$と$x-h$はそれぞれ$x$と接続された頂点と見なせるだろう。$f(x)$前の$2$は$x$と隣接する点が二つあることを意味する。したがって$(1)$をグラフの観点から見ると隣接する頂点に対する値から基準となる頂点の値を次数分だけ引いたものである。これを数式で表現すると$A - D$となるが、符号を反転させると正定値行列になるので次のように定義する。
$$ L := D - A $$
■
性質
- グラフラプラシアン $L$は正定値行列である。
証明
1.
$D = [D_{ij}]$と$A = [A_{ij}]$を$n \times n$次数行列と隣接行列とする。$\mathbf{x} \in \mathbb{R}^{n}$という。
$$ \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \mathbf{x}^{\mathsf{T}} (D - A) \mathbf{x} \\ &= \mathbf{x}^{\mathsf{T}} D \mathbf{x} - \mathbf{x}^{\mathsf{T}} A \mathbf{x} \\ &= \sum\limits_{i=1}^{n} D_{ii} x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ &= \sum\limits_{i=1}^{n} \left( \sum\limits_{j=1}^{n} A_{ij} \right) x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ \end{align*} $$
このとき、$i, j$はダミーインデックスであり、$A$は対称行列なので、$\sum_{i,j}A_{ij}x_{i} = \sum_{i,j}A_{ij}x_{j}$が成り立つ。したがって次を得る。
$$ \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} - x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( 2x_{i}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} + x_{j}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i} - x_{j} \right)^{2} \end{align*} $$
$A_{ij} \ge 0$であるため、$L$は正定値行列である。
■