---아직 작성중 입니다: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 Networks and Locally Connected Networks on Graphs
Convolutional Neural Networks are extremely efficient architectures in image and audio recognition tasks, thanks to their ability to exploit the local translational invariance of signal classes over their domain. In this paper we consider possible generali
arxiv.org
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
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or wor
arxiv.org
3. GCN (ICLR 2017)
논문 링크 : https://arxiv.org/abs/1609.02907
Semi-Supervised Classification with Graph Convolutional Networks
We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a loc
arxiv.org