이번 글에서는 Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의에 대해 알아보도록 하자. 오늘의 글을 본격적으로 진행하기 전에 몇가지를 정의하고 시작하자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $D$를 $G$의 degree matrix라고 정의하고 $A$를 $G$의 adjacency matrix라고 정의하자. 그리고 $L^{norm}$을 $G$의 normalized laplacian matrix라고 정의하자. (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유)
Graph Fourier Transform 왜 필요할까?
$G$의 vertex의 갯수 $|V|=n$이라 하자. 각각의 vertex $i$ 마다 어떠한 representation $x_i$를 갖는다고 가정하고 이 $x_i$들을 모아서 graph의 vertex의 representaion을 모두 표현하는 $x=(x_1,…,x_n)^T$를 정의하자. 관찰을 위해 Normalized Laplacian matrix $L^{norm}$과의 qudaratic form을 구해보려고 한다. 지난 글을 참고한다면 아래와 같이 $L^{norm}$에 대한 qudaratic form을 구할 수 있다.
$$x^T L^{norm} x = \sum_{i,j} A_{ij} (x_i/\sqrt{D_{ii}}-x_j/\sqrt{D_{jj}})^2$$
위의 식을 토대로 해석하면 $x^T L^{norm} x $는 인접한 vertex가 얼마나 비슷한지 볼 수 있다. $x^T L^{norm} x $가 작다면 인접합 vertex간의 표현이 비슷하다는 것이고 $x^T L^{norm} x $가 크다면 인접한 vertex들 끼리 이질적인 성격을 가졌다고 해석할 수 있다. 더 많은 관찰을 위해 $L^{norm}$를 대각화 해보자. $L^{norm}$의 symmetric postivie semi definite한 성질에 의해 $L^{norm}$은 0보다 큰 eigen value $\lambda_1,…,\lambda_n$를 갖고 이것에 대응되는 eigen vector $u_1,…,u_n$을 갖게되며 $u_1,…,u_n$은 orthonormal basis가 된다. $u_1,…,u_n$는 basis이므로 $x = \sum_{i} c_i u_i$형태로 표현이 되고 이점을 이용하면 아래와 같이 $x^T L^{norm} x$를 쓸 수 있다.
$$x^T L x = \sum_{i,j} A_{ij} (x_i/\sqrt{D_{ii}}-x_j/\sqrt{D_{jj}})^2 = \sum_{i} c_i^2 \lambda_i$$
분석을 위해 $\lVert x \rVert^2 = \sum_{i} c_i^2 = 1$이라고 가정하자. $\lambda_i$가 작은 쪽에 $c_i^2$ 값이 크다면 $x^T L x $의 값이 작아지고 그에 따라 인접한 vertex 들은 서로 비슷하다라는 것을 알 수 있다. 즉 하나의 vertex에서 연결된 edge를 타고 다른 vertex로 간다고 할 때 변화가 적다는 것을 의미한다. $\lambda_i$가 큰 쪽에 $c_i^2$ 값이 크다면 $x^T L x $의 값이 커지고 그에 따라 인접한 vertex 들은 서로 다르다는 것을 알 수 있다. 즉 하나의 vertex에서 연결된 edge를 타고 다른 vertex로 간다고 할 때 변화가 크다는 것을 의미한다. 그런점에서 각각의 $\lambda_i$는 vertex에서 신호를 보내서 edge를 타고 갔을 때 얼만큼 변하는지 나타내는 일종의 frequency에 대응된다고 볼 수 있고, $\lambda_i$에 대응되는 $c_i$는 이 frequency 에 성분이 얼마나 있는지를 나타낸다. frequency에 성분이 얼마있는지 라는 말을 썼는데 spectral 분석이라는 용어도 쓰는 것 같다.
Graph Fourier Transform의 정의와 의미
그러면 앞서 말한 motivation 으로 $\lambda_i$에 대응하는 $u_i$성분인 $c_i$가 얼마나 있는지를 분석하기 위하여 Graph Fourier Transform을 정의한다. $L^{norm}$은 대각화가 되기 때문에 $L^{norm} = U\Lambda U^T$라고 표현할 수 잇고 $U$의 각 column 은 $u_i$이고 $\Lambda$의 대각선 성분은 $\lambda_i$가 된다. 위에서 처럼 $x=(x_1,…,x_n)^T$를 각각의 vertex의 representation $x_i$를 모아둔 벡터라고 할 때 Graph Fourier Transform은 아래와 같이 정의한다.
$$\hat{x} = U^T x \tag{Graph Fourier Transform}\label{Graph Fourier Transform}$$
$x = \sum_{i} c_i u_i$형태이므로 $\hat{x} = (c_1,…,c_n)^T$가 나오는 것을 확인할 수 있고 여기서 $c_i$는 각각의 frequency $\lambda_i$에 성분이 얼마나 있는지 나타낸다.
Graph Inverse Fourier Transform
Graph Inverse Fourier Transform은 Fourier Transform을 다시 node에 관한 representation으로 만드는 것이다. 아래와 같이 정의한다.
$$x = U \hat{x} \tag{Graph Inverse Fourier Transform}\label{Graph Inverse Fourier Transform}$$