---아직 작성중 입니다:D---
* 이 글은 서울대학교 최진영 교수님의 Graph Convolution Networks 강의를 듣고 요약한 글입니다! 좋은 강의를 들려주신 최진영 교수님께 감사합니다. :)
앞서 GCN 1편 포스팅에서는 graph theory에서 맨 처음 마주하는 laplacian, fourier transform에 대해서 알아보았다면
이번 포스팅에서는 이를 기반으로 GNN model들이 어떻게 발전해왔는지 정리해보고자 합니다!! :D
먼저 spectral domain에서 convolution 연산을 수행하는 Spectral GCN을 시작으로, Spectral GCN에서 사용되는 fourier coefficient의 polynomial식을 더 stable하게 개조한 ChebNet, 마지막으로 spectral 및 spatial domain을 연결해 준 GCN에 대해서 다뤄보록 하겠습니다.
1. Spectral GCN (ICLR 2014)
논문 링크 : https://arxiv.org/abs/1312.6203
Spectral GCN은 앞서 GCN 1편 포스팅에서 말씀드린 Spectral Filtering을 이용하는 방법입니다. 자세한 내용은 1편 포스팅 3. Fourier Transform 이후를 참고해 주세요!~
다시 한 번 살펴보면, 위 그림에서 보듯 Graph Fourier Transform(GFT)을 통해 graph signal을 fourier coeffiecient로 변환합니다. 이후 laplacian matrix의 eigenvalue들을 기반으로 어떤 signal을 사용할 지 함수화한 filter g(Λ)를 곱하여 중요한 signal만 남기게 됩니다. 이후 Inverse Graph Fourier Transform(IGFT)을 이용하여 graph signal f를 reconstruct하는데, 이 때 결과적으로 f앞에 Ug(Λ)U^{T}가 곱해지는 것을 볼 수 있습니다. UΛU^{T}는 laplacian 행렬 L이므로 결과적으로 graph filtering의 최종 결과는 g(L)f로 나타낼 수 있습니다.
위 그림은 같은 내용을 model구현을 위한 행렬식으로 표현한 것으로, N * d1 크기의 input feature를 N * d2 크기의 output feature로 변환하는 그림입니다. 맨 아래 수식은 output feature의 n번째 channel feature를 형성하는 과정입니다. d1개의 input feature의 channel에 대해, d2 * d1 크기의 filter g(L)를 곱하여 output space로 mapping해줍니다. 딥러닝을 공부하시며 많이 보셨을 일반적인 행렬 연산이라 쉽게 느껴지실 듯 합니다! :)
위 그림에서 볼 수 있듯이 deep learning 이전의 graph filtering 방식들은, laplacian matrix L의 eigenvalue λ 중 작은 것만(Low-pass, 비슷한 signal정보만 이용), 큰 것만(High-pass, 서로 다른 signal정보만 이용) 사용하는 등 미리 정의된 의도에 따른 함수 g^을 filter로 사용하였습니다. 따라서 행렬 g^(Λ)는 non-parametirc, not-learnable하다고 할 수 있습니다.
따라서 Spectral GCN에서는, 이미 정의된 함수를 g^으로 사용하는 대신 g^을 eigenvalue λ들의 polynomial 함수로 정의하였습니다. 또한 주로 Low-pass filter를 많이 사용하므로, N개의 eigenvalue 중 K개까지만 polynomial함수로 표현하여 parameter수를 줄였습니다. 따라서 결과적으로 빨간 박스 안의 식과 같이, 기존의 IGFT수식을 맨 오른쪽 항과 같이 표현할 수 있게 되고, 결과적으로 laplacian matrix L을 사용하므로 eigen-decomposition이 필요하지 않게 됩니다. 최종 식은 결국 모든 차원 d1에 대해 ΣθL을 곱하여 합하므로, spatial공간에서의 연산과 비슷한 형태를 갖게 됩니다.
따라서 spectral GCN에서는 over-smoothing을 방지하기 위해, i번째 node에 대해 filter ΣθL를 곱할 때, K-hop 떨어진 node j에 대해서는 filter 값을 강제로 0으로 정의하였습니다. 결과적으로 spectral GCN은 eigenvalue의 polynomial함수로 filter g를 정의하여 spectral domain에서의 graph filtering을 parameterization하였습니다.
2. ChebNet (NIPS 2016)
논문 링크 : https://arxiv.org/abs/1606.09375
3. GCN (ICLR 2017)
논문 링크 : https://arxiv.org/abs/1609.02907