Spectral GCN에서 Fourier Transform을 하는 이유

Contents

 

Fourier Transform을 사용하는 이유를 다루기에 앞서 기본적인 선행 지식이 요구되기에 Laplacian이 무엇인지 부터 짚고 넘어가자. Laplacian operator는 기울기를 확인하기 위한 연산자 정도로만 이해하면 된다. 그래프는 euclidean space에서 정의할 수 없기 때문에 mainfold 구조에서의 Graph signal을 통해 신호를 확인하려고 하는 것이다. 이때 Graph signal은 node가 가지고 있는 feature를 의미한다. 예를 들어, social network의 경우에는 해시태그의 수가 될 수 있고, 연령 등의 정보가 될 수 있다. 

 

Euclidean space에 있는 다양체를 리만 다양체에서 정의된 함수로 일반화 하는 과정을 Laplace Beltrami Operator라 부르며, 변환한 후 이를 통해 두 점 사이의 거리 혹은 곡률을 측정할 수 있다. 리만 다양체(Riemannian manifol)는 두 점 사이의 거리 혹은 곡률을 측정할 수 있는 하나의 다양체라고 볼 수 있다. 리만 다양체를 이용해 다양체 위에서 각도, 길이, 부피, 곡률 등 다양한 기하학적 개념을 정의할 수 있다. 

 

Spectral Graph Convolution Network에서는 이미지나 음성 등과 같은 도메인에서 2D Convolution Filter를 사용하지 않고, Graph Convolution을 구성할 때 Fourier Transform을 사용하여 신호를 추출한다. 그렇다면 왜 다른 방식을 사용할까? 이미지에서는 기본적으로 Spatial Domain을 의미한다. Spatial Domain은 공간 상에 있다는 것을 의미하며 아래의 그림을 확인하면 보다 쉽게 이해할 수 있다. 

 

좌: 2D Convolution, 우: Graph Convolution

이미지나 다른 도메인에서 사용하는 2D Convolution Filter를 사용해 Spatial한 정보를 추출할 수 있다. 그러나 그래프의 구조에 2D Convolution을 통해 연산을 수행하기에는 Filter를 지정하는 것이 애매하다. 따라서, 이와 같은 연산을 수행하기 위해 기존의 연산을 Fourier Transform을 통해 가능하도록 만드는 것이다.

\[ \begin{equation} \begin{split} \text{2D Convolution}  : f * g(x) & = \sum_y f(y) g(x-y) \\ \text{Graph Convolution} : f * g(x) & = \mathcal{F}^{-1} \{  \mathcal{F}(f) \mathcal{F}(g) \} \end{split} \end{equation} \]

$g(x)$는 filter를 의미하고, $x$는 실제 값 $y$는 계산한 값 $g(x-y)$는 실제값과 계산한 값 간의 차이 즉 error를 의미한다. $f * g(x) = \mathcal{F}^{-1} \{  \mathcal{F}(f) \mathcal{F}(g) \}$ 해당 수식은 Graph Convolution Theorem을 의미하며, 이는 $f$와 $g$를 Frequency Domain으로 변환하여 다시 역변환을 수행해 Convolution을 수행하자는 뜻이다. 

 

Spectral Graph Processing

\[ f \rightarrow \chi^T f \rightarrow \hat{g}(\Lambda) \chi^T f \rightarrow \chi \hat{g}(\Lambda)\chi^T f \]

$\chi^T$와 $\hat{g}(\Lambda)=\Lambda$는 Graph의 Eigenvector와 Eigenvalue를 의미한다. 갑자기 Eigenvector와 Eigenvalue가 등장해서 당황할 수 있으나, 우리가 위에서 구한 Laplacian Matrix가 바로 이를 통해 계산된다. 기본적으로 Graph 신호에서의 Fourier Transform은 Laplacian matrix를 eigen-decomposition하는 것이기 때문에 Graph Fourier Transform과 Graph Inverse Fourier Transform을 통해 eigen-decomposition을 구하는 것이다(해당 개념은 PCA를 확인!). 행렬을 고유분해 할 경우 수식은 $\text{L} = \chi \hat{g}(\Lambda) \chi^T $가 되는 것이다. 이때 $\text{L}$은 Leplacian matrix를 의미한다. 

 

위 연산은 Laplacian matrix $\text{L}$의 미분 연산을 의미한다. 그렇다면 Laplacian quadratic form은 어떻게 될까? 기본적으로 행렬에서는 제곱꼴을 다룰 때 전치 행렬을 앞에 곱하는 형태로 진행한다. 예를 들어, $a*x$를 제곱한다면, $x^T*a*x$가 되는 것이다. 

\[ f^T \text{L} f = || \text{L}^{\frac{1}{2}} f ||_2 = ||\chi \Lambda^{\frac{1}{2}} \chi^T f ||_2 \]