그래프 라플라시안
정의
그래프 $G$의 차수행렬를 $D$, 인접행렬를 $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$은 양의 정부호 행렬이다.
■