* 이 글은 서울대학교 최진영 교수님의 Graph Convolution Networks 강의를 듣고 요약한 글입니다! 좋은 강의를 들려주신 최진영 교수님께 감사합니다. :)
Graph Neural Network를 공부하다 보면, 시작부터 Graph Laplacian과 Fourier Transform을 마주할 수 있게 됩니다. ㅠㅠ 이 글에서는 Graph Laplacian과 Fourier Transform이 왜 필요한지, 그 내용은 무엇인지에 대해서 이야기하도록 하겠습니다! 저도 수학을 잘 몰라서(ㅠㅠ), GNN을 사용하는 데 가장 필요하다고 생각되는 기본적인 내용 위주로 다루도록 하겠습니다. 또한 기본적인 graph의 구조(node, edge)에 대해서는 안다고 가정하고 설명하도록 하겠습니다.
1. Graph Laplacian과 Fourier Transform이 필요한 이유
예를 들어, image QA 문제를 풀기 위해 GNN을 적용한다고 가정하겠습니다. 만약 하나의 이미지로부터 N개의 object를 추출하였다면, GNN을 사용하는 경우 각 object의 spatial relationship을 표현할 수 있게 됩니다. 예를 들어, 탁자에 컵이 놓여져 있다면 탁자 feature와 컵 feature는 연결된 edge로 표현하고, 그 외 관련 없는 object와는 edge를 제거하여 graph로 표현할 수 있습니다. 이렇듯 GNN을 사용하면 이미지 내에서의 정보를 더욱 풍부하게 표현할 수 있습니다.
결론부터 말씀드리면, Graph Laplacian Quadratic Form은 주어진 그래프에서 하나의 node에 대해 연결된 주변 node와의 difference값을 합산한 것입니다. 따라서 그래프의 edge matrix가 정의된 경우 이 quadratic form을 minimize하면, 관련된 주변 정보를 반영한 새로운 feature를 얻을 수 있습니다. 따라서 graph laplacian quadratic form은 graph filtering(=node embedding)을 위한 objective function이라고 생각할 수 있습니다. 실제로 GCN 논문(https://arxiv.org/abs/1609.02907)을 보시면, GCN 이전의 graph-based semi-supervised learning 연구들은 node classification을 위해 classification loss term에 laplacian regularization term을 추가해주는 것을 볼 수 있습니다!
다음으로 Graph Fourier Transform은, spectral domain에서 graph filtering을 하기 위한 방법입니다. Graph Fourier Transform을 사용하여 graph signal을 spectral domain으로 변형한 후, 다시 spatial domain으로 변형하면 graph filtering을 할 수 있습니다. 자세한 방법은 아래에서 설명하도록 하겠습니다!
2. Graph Laplacian이란?
그림과 같이 그래프가 주어졌을 때, vertex(node)의 feature를 나타내는 graph signal f와 edge의 연결 여부를 나타내는 matrix A를 위와 같이 정의할 수 있습니다.
이 때 Laplacian Matrix L은 위와 같이 Degree Matrix D에서 Adjacency Matrix A를 뺀 행렬로 정의됩니다.
이 Laplacian matrix L에 graph signal f를 곱하면 아래와 같이 difference operator로서 의미를 갖게 됩니다.
수식을 자세히 들여다 보면, h_i는 결국 (하나의 node feature * 연결된 수), 즉 D_ii*f_i에서 (연결된 node feature들), 즉 A_i*f를 뺀 값이 됩니다. 결과적으로 하나의 node feature f_i에 대해 연결된 neighbor node feature f_j들을 뺀 값을 의미하므로 difference operator가 됩니다.
그러나 이러한 경우, 단순히 차이를 합한다는 데 한계가 있습니다. 절댓값 또는 제곱을 취하지 않은 채 difference값들의 단순 합을 통해 부호가 상쇄되므로, h값이 0에 가깝다고 f_i와 neighbor node feature간에 유사도가 크다고 하기 어렵습니다.
따라서 아래와 같이 Laplacian Quadratic Form을 정의하게 됩니다:
단순히 L과 f를 곱하는 대신 f를 두 번 곱해 제곱 형태로 만들면, 맨 아래 수식이 유도됩니다.
따라서 f^{T}Lf는 두 node가 연결된 경우, node feature간의 difference를 제곱합 한 값을 의미하게 됩니다.
결과적으로 quadratic 값이 작을수록 neighbor node와 유사하다는 의미를 갖게 됩니다!
따라서 주어진 그래프에 대해, 연결된 node끼리 feature를 유사하게 하고 noise를 제거하여 graph node feature를 update하고 싶은 경우(=graph filtering, smoothing) 위 quadratic form을 최소화하는 f를 구하면 됩니다!!!
3. Graph Fourier Transform
3-1) Laplacian Quadratic form의 의미
앞서 우리는 laplacian quadratic form에 대해 살펴보았습니다. 위 그림의 왼쪽에서 볼 수 있듯이, laplacian quadratic form은 결과적으로 signal f의 "smoothness" 또는 "frequency"를 의미하며, signal f를 이러한 frequency의 집합으로 나타내어 연산하고자 하는 것이 spectral graph theory 입니다. 그림의 오른쪽에서 볼 수 있듯이 quadratic form 값이 크면 graph signal 간의 difference가 큰 것이므로, high frequency를 가졌다고 볼 수 있습니다. 반대로 quadratic 값이 작으면 low frequency를 가졌다고 볼 수 있습니다.
그렇다면 Laplacian quadratic form의 solution은 무엇일까요? 위 그림과 같이 form을 minimize하도록 하는 최적의 f를 구해 보면, f는 laplacian matrix L의 eigenspace에 속하는 벡터라고 합니다. 즉 L의 eigenvector들이 해당 form을 최소화하는 것을 알 수 있습니다.
이미 선형대수 시간에 다들 배우셔서 아시는 친숙한 식입니다. :) Laplacian matrix L의 eigenvector w와 eigenvalue λ는 위 그림과 같은 수식을 만족하게 되는데요! 위 수식에서 w를 좌변으로 넘기면
위와 같은 수식이 됩니다! (u는 w와 같은 eigenvector라고 보시면 됩니다!) 즉 수식의 맨 왼쪽 항 u^T*L*u는 laplacian quadratic form과 같은 형태로 graph signal의 smoothness를 나타내고, 맨 오른쪽 항 λ는 L의 eigenvalue입니다. 즉 laplacian matrix L을 eigen decomposition하면, N개의 eigenvector와 eigenvalue를 얻을 수 있고, 각각의 eigenvalue는 각각 eigenvector signal u들의 smoothness를 의미하게 됩니다! 위 그림에서는 eigenvalue를 작은 것 부터 λ1, λ2, ...로 나열한 것입니다.
3-2) Graph Fourier Transform
그렇다면 laplacian quadratic form이 graph signal의 smoothness를 의미하며, laplacian matrix L eigenvalue가 이것을 의미한다는 것을 잘 알았습니다. 이것이 graph fourier transform과 관련이 있는 이유는 무엇일까요?
결론부터 말씀드리면, 위 그림과 같이 Graph Fourier Transform은 laplacian matrix L을 eigen decomposition하여 eigenvector들의 합으로 signal f를 표현하는 것 입니다. 즉 graph signal을 기존의 spatial공간에서 frequency를 나타내는 spectral공간으로 변환하는 것입니다!
이것의 의미는, 작은 eigenvalue를 갖는 eigenvector의 경우 graph를 더욱 smooth하게 나누는 기준이 되며, node간의 유사한 특징 정보를 담고 있다고 할 수 있습니다. 반대로 큰 eigenvalue를 갖는 eigenvector의 경우 node간 서로 다른 특징의 정보를 많이 담고 있다고 할 수 있습니다.
3-3) Graph Fourier Transform으로 Spectral Filtering
그렇다면 굳이 spatial domain에 있던 signal 정보를 왜 spectral domain으로 보내는 것일까요? 그 이유는 graph signal을 frequency의 조합인 spectral domain에서 표현한 후, 다시 spatial domain으로 복원할 때 사용되는 filter를 학습함으로써 graph signal의 noise를 제거하고 필요한 성분만을 남겨 node를 embedding하기 위해서 입니다.
위 그림에서 보실 수 있듯이, GFT (Graph Fourier Transform)을 통해 signal f를 decompose합니다. 이후 g(λi)를 곱하여 IGFT (Inverse Graph Fourier Transform)을 연산하고, 다시 spatial 공간으로 정보를 보내는데요. 이 때 g(.)는 학습해야 할 filter 입니다. filter g는 여러개의 frequency 신호 중 어떤 것을 사용해야 할 지 거르는 역할을 합니다. 그림에서 오른쪽 위 두 그래프를 보시면, f^i는 fourier 계수(frequency)를, g^는 filter를 의미합니다. 그림에서의 filter를 사용하면 앞 쪽에 있는 frequency들만 사용하고, 뒤 쪽에 있는 frequency들은 사용하지 않게 됩니다.
4. GNN model들의 발전 과정
위 그림에서 볼 수 있듯이, 이전의 GNN 모델들 (~ChebNet)은 앞서 설명드린 graph spectral theory를 바탕으로 graph filtering을 해 왔다는 것을 볼 수 있습니다. 그러나 Kipf & Welling의 GCN논문이 ICLR에 발표되면서, 이후의 모델들은 대부분 spatial domain에서 편안하게 연산을 하기 시작했습니다. GCN논문은 대략적으로 말씀드리면, spectral domain에서 하던 convolution 연산을 spatial domain에서도 매우 간단하게 할 수 있다! 는 내용인데요. 이후의 포스팅에서는 ChebNet, GCN부터 GAT까지 GNN의 근간이 되는 모델들에 대해 빠르게 살펴보도록 하겠습니다! :)