logo

グラフラプラシアン 📂グラフ理論

グラフラプラシアン

定義

グラフ GGの次数行列をDD、[隣接行列](../1499）をAAとする。このとき、GGのグラフラプラシアンgraph Laplacian LLは次のように定義される。

L:=D−A L := D - A

説明

ユークリッド空間上の関数に対して定義されるラプラシアン Δ=∑i∂2∂xi2\Delta = \sum\limits_{i} \frac{\partial^{2}}{\partial x_{i}^{2}}とは異なり、与えられるグラフに依存する。

グラフ G=(V,E)G = (V, E)に対して f:V→Rf : V \to \mathbb{R}をノードシグナルとし、f=[f(v1)⋯f(vn)]T\mathbf{f} = \begin{bmatrix} f(v_{1}) & \cdots & f(v_{n}) \end{bmatrix}^{\mathsf{T}}のように表記しよう。すると、LfL\mathbf{f}の各成分は各頂点vertexにおける値が隣接する頂点の値とどれだけ差があるかを示している。

導出

多変数関数 g:Rn→Rg : \mathbb{R}^{n} \to \mathbb{R}に対してラプラシアンは次のように定義される。

∇2g=Δg=∂2g∂x12+⋯+∂2g∂xn2 \nabla^{2} g = \Delta g = \dfrac{\partial^{2} g}{\partial x_{1}^{2}} + \cdots + \dfrac{\partial^{2} g}{\partial x_{n}^{2}}

実数空間上で定義された関数 f:R→Rf : \mathbb{R} \to \mathbb{R}の微分係数は次のように数値的に近似できる。

f′(x)=f(x+h)−f(x)h f^{\prime}(x) = \dfrac{f(x+h) - f(x)}{h}

f′′(x)=f(x+h)−2f(x)+f(x−h)h2(1) f^{\prime \prime}(x) = \dfrac{f(x+h) - 2f(x) + f(x-h)}{h^{2}} \tag{1}

この式をグラフに対して考えてみよう。xxを頂点と見なすと、x+hx+hとx−hx-hはそれぞれxxと接続された頂点と見なせるだろう。f(x)f(x)前の22はxxと隣接する点が二つあることを意味する。したがって(1)(1)をグラフの観点から見ると隣接する頂点に対する値から基準となる頂点の値を次数分だけ引いたものである。これを数式で表現するとA−DA - Dとなるが、符号を反転させると正定値行列になるので次のように定義する。

L:=D−A L := D - A

■

性質

  1. グラフラプラシアン LLは正定値行列である。

証明

1.

D=[Dij]D = [D_{ij}]とA=[Aij]A = [A_{ij}]をn×nn \times n次数行列と隣接行列とする。x∈Rn\mathbf{x} \in \mathbb{R}^{n}という。

xTLx=xT(D−A)x=xTDx−xTAx=∑i=1nDiixi2−∑i,j=1nAijxixj=∑i=1n(∑j=1nAij)xi2−∑i,j=1nAijxixj \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,ji, jはダミーインデックスであり、AAは対称行列なので、∑i,jAijxi=∑i,jAijxj\sum_{i,j}A_{ij}x_{i} = \sum_{i,j}A_{ij}x_{j}が成り立つ。したがって次を得る。

xTLx=∑i,j=1nAij(xi2−xixj)=12∑i,j=1nAij(2xi2−2xixj)=12∑i,j=1nAij(xi2+xj2−2xixj)=12∑i,j=1nAij(xi−xj)2 \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*}

Aij≥0A_{ij} \ge 0であるため、LLは正定値行列である。

■