Fourier transform for Graph

앞에서 살펴봤던 Fourier transform을 신호(signal) 뿐만 아니라 Graph 분야에서도 사용할 수 있다.

 

Graph안의 node들은 시간 t 가 흐름에 따라 주변 이웃 node들의 정보를 포함하게 된다.

 

시간 t에 따라 노드가 포함하는 이웃 노드의 정보가 바뀐다.

위 그림에서 노드 "3"을 살펴보자.

시간 t가 지남에 따라 주변 이웃 노드들(1-hop 외에 더 넓은 범위의 이웃까지)의 feature(signal)를 포함하여 매시간 t마다 다른 signal을 가지는 것을 볼 수 있다.

이를 time domain/spatial domain에 나타낸 모습이 왼쪽 그림이다.

위의 예시에서, 각 노드는 2-dimension의 feature vector를 가지는데 signal(0)은 feature vector의 index 0 에 해당하는 value, signal(1)은 feature vector의 index 1에 해당하는 value이다. 시간이 지남에 따라 해당 노드의 이웃 노드들의 feature vector의 합(각 index의 값을 합한다)이 해당 노드를 나타내는 feature vector가 된다. 즉, t=1에서 node 3의 signal(0)은 7 크기 t=2에서는 3의 크기를 갖는 것을 볼 수 있다.

 

이렇게 여러 이웃 노드들의 feature(signal)을 시간에 따라 한꺼번에 포함하여 복잡한 signal을 생성하는 graph의 특징을 바탕으로 spectial analysis를 수행하면 각 노드의 복잡한 feature(signal)를 단순한 여러 feature(signal)들의 합으로 나타내 더 효과적으로 분석할 수 있게된다.

•  Fourier transform 같은 방법으로 time/spatial domain에서 frequency domain으로 변환하는 것을 spectral analysis라고 한다.
• Graph나 Computer vision 분야에서는 spatial domain, 신호처리 같은 분야에서는 time domain

 

이전 포스트에서 Fourier transform은 복잡한 신호를 time domain이 아닌 frequency domain에 나타냄으로써 복잡한 신호를 단순한 element들의 선형결합으로 나타내는 것이라고 설명했었다.

Fourier Transform 이란?

Fourier transform

위의 푸리에 변환식에서 \(e^{-2\pi ix\xi}\)가 orthonormal basis(직교 기저 함수)일때 원본 신호인 \(f(x)\) 와 내적을 통해 amplitude 를 뜻하는 계수 \(\hat{f(\xi)}\)를 구할 수 있다.

graph 관점에서 이러한 orthonormal basis를 구하는 방법이 바로 eigen decomposition이다.

• symmetric matrix에 대해 eigen decomposition을 수행하여 얻어진 eigenvector들은 orthonormal basis이다.

이때 구해진 eigenvector 들의 선형 결합으로 원본 신호 \(f(x)\)를 생성할 수 있고 원본신호 \(f(x)\) 와 구해진 eigenvector들의 내적으로 계수를 구하는 것을 Fourier transform으로 볼 수 있는 것이다.

 

이 모든 것을 통합해보면 graph에서의 Fourier transform은 graph의 laplacian matrix를 eigen decomposition(spectral decomposition)하는 것으로 볼 수 있다.

 

[Laplacian matrix 의 특징]

• symmetric
• non-positive off-diagonals
• diagonally dominant

 

Graph 안의 node들은 주변의 자신과 비슷한 특징을 가진 이웃과 그렇지 않은 이웃들의 신호를 시간이 지남에 따라 모두 포함하게 되는데 유사한 이웃 노드의 신호와 그렇지 않은 노드의 신호를 구분하기 위해서 노드 간의 variation의 정도를 나타내는 laplacian matrix를 사용하여 푸리에 변환을 수행하는 것이라고 볼 수 있다. (variation이 작을 수록 비슷한 특성을 가진 이웃 node)

 

[reference]

Graph Convolutional Network에 대하여 - Spectral Graph Convolution · Ralasun Resarch Blog