이번 글에서는 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 이것의 eigen value가 0과 2사이라는 사실을 설명해보겠다. Normalized Laplacian matrix에 대해 알아보기 전에 Normalized adjacency matrix를 정의하고 그것으로 부터 Normalized Laplacian matrix를 정의한 이 후 글을 이어가겠다.
Normalized Laplacian matrix 알아보기
그래프 $G=(V,E)$가 있다고 하자. $V=\{1,2,…,n\}$이라고 편하게 표시하자.
Nomralized Adjacency matrix 정의
Normalized Laplacian matrix에 대해 알아보기전에 Normalized adjacency matrix에 대해 알아보자. 말그대로 Normalized 된 adjacency matrix 이다. $D$를 $G$의 degree matrix라고 하고 $A$를 $G$의 adjacency matrix 라고 하자. (degree matrix와 adjacency matrix에 대해서는 지난 Laplacian matrix를 설명하는 글에서 정의되었다.) Normalized adjacency matrix $A^{norm}$은 아래와 같이 정의한다.
$$A^{norm} = D^{-1/2} A D^{-1/2} \tag{Normalized adjacency matrix}\label{Normalized adjacency matrix}$$
$A^{norm}$ i번째 row, j번째 column의 원소는 $A^{norm}_{ij} = \frac{A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}}$ 임을 알 수 있다. $D_{ii} = \sum_{k} A_{ik}, D_{jj} = \sum_{j} A_{ik}$이고 이 합들을 구성하는 원소중에 하나가 $A_{ij}$이므로 $A^{norm}_{ij}$는 $A$를 normalized 한 형태라고 볼 수 있겠다.
Normalized Laplacian matrix
Laplacian matrix $L:=D-A$라고 지난 글에서 정의 했었다. Normalized Laplacian matrix는 아래와 같이 정의한다.
$$L^{norm} = D^{-1/2} L D^{1/2} = I – A^{norm} \tag{Normalized Laplacian matrix}\label{Normalized Laplacian matrix} $$
Normalized adjacency matrix와 마찬가지로 $D$에 대하여 normalized 하였다. $L$자체가 symmetric 이고 (참고), $D^{-1/2}$가 symmetric 이므로 $L^{norm}$또한 symmetric이다. 이제 Normalized Laplcian matrix $L^{norm}$이 positive semidefinite matrix임을 보이고 eigen value의 upperbound가 2임을 보이자.
Normalized Laplacian matrix가 positive semidefinite matrix인 이유
$x=(x_1,x_2,…,x_n)^T$라고 하자. $D,A$가 symmetric matrix이라는 사실과 $D_{ii} = \sum_{j} A_{ij}$라는 사실을 이용하면 $L^{norm}$이 positive semidefinite matrix라는 것을 보일 수 있다.
$$\begin{align} x^T A^{norm} x &= x^Tx – x^T A^{norm} x \\ &= \sum_{i} x_i^2 -\sum_{i,j} \frac{x_i x_j A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}}\\ &= \sum_{i} x_i^2 \frac{ D_{ii}}{\sqrt{D_{ii}}\sqrt{D_{ii}}} -\sum_{i,j} \frac{x_i x_j A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}}\\ \\ &= \frac{1}{2}\left( \sum_{i} x_i^2 \frac{ D_{ii}}{\sqrt{D_{ii}}\sqrt{D_{ii}}} +\sum_{j} x_j^2 \frac{ D_{jj}}{\sqrt{D_{jj}}\sqrt{D_{jj}}} -2\sum_{i,j} \frac{x_i x_j A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}}\right)\\&= \frac{1}{2}\left( \sum_{i} x_i^2 \frac{\sum_j A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{ii}}} +\sum_{j} x_j^2 \frac{ \sum_{i}A_{ij}}{\sqrt{D_{jj}}\sqrt{D_{jj}}} -2\sum_{i,j} \frac{x_i x_j A_{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}}\right) \\ &= \frac{1}{2} \sum_{i,j} A_{ij} \left( x_i/\sqrt{D_{ii}} – x_j / \sqrt{D_{jj}}\right)^2 \geq 0 \end{align}$$
따라서 normalized Laplacian matrix $L^{norm}$가 positive semidefinite 임을 보였다.
Normalized Laplacian matrix의 eigen value가 0과 2사이인 이유
Normalized Laplacian matrix $L^{norm}$는 symmetric이므로 실수값의 eigen value를 갖고 postive semidefinite 이므로 eigen value는 0보다 크거나 같다. 그러면 eigen value는 2보다 작거나 같을까? $x$를 $L^{norm}$의 eigenvalue $\lambda>0$에 대응하는 eigen vector라고 하자. 그러면 위의 계산과 비슷하게
$x^T (I + A^{norm}) x = \frac{1}{2} \sum_{i,j} A_{ij} \left( x_i/\sqrt{D_{ii}}+ x_j / \sqrt{D_{jj}}\right)^2 \geq 0 $임을 알 수 있다. 이 사실을 이용하여 아래와 같은 사실을 알 수 있다.
$$x^T L^{norm} x = x^T (I – A^{norm})x = x^Tx -x^TAx \leq 2x^T x \Rightarrow \lambda x^T x =x^T L^{norm} x \leq 2 x^Tx$$
따라서 $\lambda \leq 2$라는 사실까지 알 수 있다.
이번 글에서는 Normalized Laplacian matrix의 정의를 했다. Normalized Laplacian matrix가 symmetric이고 positive semidefinite matrix임을 알게 되었고 eigen value가 0부터 2사이임을 알게되었다. 이 점을 이용해서 graph에서 fourier transform을 정의할 수 있는데, 이것에 대해서는 나중에 보도록 하자.
Reference
https://harryjo97.github.io/theory/Graph-Laplacian/
https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf