GCN paper review
본격적으로 논문 리뷰를 하기에 앞서 본 리뷰는 다음 영상을 참고하여 작성하였다.
https://www.youtube.com/watch?v=F-JPKccMP7k
혼자서 여러 자료들과 논문들을 통해 이해하려고 하였고, semi-supervised learning에 관한 설명에 대한 글도 올렸었다.
이후, normalized graph laplacian, fourier transform in GCN, 1st order approximation in GCN, Chebyshev polynomials, spectral convolutions, fourier domian to spatial domain 등 글을 작성하기엔 너무 많기도 하며 어려웠기에 영상을 보면서 공부하게 되었다.
GNN이란?
Graph와 관련된 모든 nerual network는 GNN이라고 생각하면 된다. 따로 분류된 것이 아닌 통틀어서 부르는 이름이라고 한다.
Convolution on Graph
"Convolution Neural Network"에서는, 이미지에 대하여 filter를 통해 정보들을 aggregate해 나가는 과정을 거쳤었다.
깊게 이야기해보자면, Convolution이란, f, g 가운데 하나의 함수를 반전, 전이 시킨 다음 다른 하나의 함수와 곱한 결과를 적분함을 뜻한다.
수식은 다음과 같다
이는 곧 현재의 합성곱의 값은 이전 시간의 결과를 포함한다. 라는 의미로 알 수 있다.
어떠한 소리 영역이 있을 때, 하나의 소리가 생성된 뒤에는 점차 줄어들게 되는 와중에 다른 소리가 생성되면 소리가 중첩이 되어 발생하는 소리보다 더 큰 소리를 듣게 된다. 이는 두 함수의 합성곱으로 인한 예시를 간략하게 든 것이다.
하고싶었던 말은, Convolution은 이미지에서만 사용되는 개념이 아니라는 것이다.
- Graph에 Conv filter를 적용하여, 하나의 노드의 인접 노드와의 관계를 알 수 있다.
- Conv는 전체 데이터에서 local feature를 뽑아낼 수 있다.
- Filter들이 불변 특징이 있다.
위와 같은 내용은 Convolution in Graph의 특징이다.
다만, 이 Convolution이 CNN에서 쓰이는 방법과 다르게 써야한다. 이는 기존 CNN같은 경우 restricted 규격의 이미지 사이즈 내에서 정의되었고, 모든 데이터가 같은 크기였다. 하지만, Graph같은 경우 노드별 degree가 다르기때문에 filter가 모든 데이터에 대해 같은 크기가 될 수 없다.
그러면, 어떻게해서 Convolution을 해야할까? Domain을 transform하는 것이다.
그래서 나온 것이 "Convolution Theorem"이다.
Convolution Theorem
- 한 Domain의 Convolution은 다른 Domain의 point-wise multiplication과 같다.
- Graph Domain의 Convolution은 Fourier Domain의 point-wise multiplication과 같다.
- Convolution의 Laplacian Transform은 point-wise multiplication으로 변한다.
이러한 Convolution Theorem을 정의하는 Graph Convolution은 두 측면이 존재한다.
- Spectral Convolution : Graph Convolution을 Graph Signal Processing의 하나의 과정으로 그래프 내의 noise 제거 과정으로 학습을 진행할 수 있다. 그리고, 주파수 영역의 Spectrum에서 원하는 주파수를 Filtering하는 목적을 가진다.
- Spatial Convolution : 공간에 대한 Convolution, Node 주위의 이웃 feature로 update를 진행한다.
본 논문에서 제안하는 GCN은 Spectral Convolution 계산으로 Spatial Convolution을 반환하게끔 하였다.
Spectral Convolution으로 전반적인 계산을 하기엔 비용이 크기에 간단한 Spatial Convolution을 도입한 것이다.
모델이 복잡하게 Spectral Conv와 Spatial Conv를 사용하는 이유에 대해서는 수학적 증명이 뒷받침된다고 이야기 하고 있다.
이제, GCN이 학습을 진행하면서 도달하고자 하는 목표는 무엇일까?
semi-supervised learning이므로 먼저, Supervised Loss를 labeled data를 통해 학습을 진행하면서, Inference로는 unlabeled data를 통해 진행(test)
Introduction
본 논문의 시작은 Graph-based semi-supervised learning의 문제제기이다.
손실함수는 지도학습의 손실율과 규제에 대한 손실에 가중치 요소가 곱해진 것으로 표현된다.
이때, 규제에 대한 손실은 연결된 노드들은 같은 label을 가질 가능성이 높다는 것을 위한 수식이다.
But, 논문에서는 이러한 규제가 모델의 표현력을 제한시켜버린다는 것을 지적하였다.
간선이 Similiarity 이상의 정보를 담을 수 있으므로, 이러한 표현력 제한은 성능 저하를 초래할 수 있다고 하였다.
Fast Approximate Convolutions on Graphs
본 논문은 아래와 같은 순전파 구조를 통해 학습을 진행하고자 한다.
이 수식이 first-order approximation of localized spectral filters on graph로 왜 될 수 있는지 알아보자.
이를 위해서는 먼저, Spectral Graph Convolution에 대해 자세히 알아봐야한다.
Spectral Graph Convolution
그래프에 대한 Spectral Convolution은 Signal x와 filter g와의 곱으로 표현된다. 자세한건 아래의 그림과 같다.
디지털 신호처리에 관한 domain은 Fourier Transform을 적용해야하는데 위와 같은 수식이 Graph Fourier Transform이다.
간단하게 Graph Fourier Transform에 대한 설명을 하자면 그래프의 Signal을 Freqeuncy별로 분해함을 뜻한다. (기존의 의미와 똑같다)
하지만, Graph에서 말하는 Signal은 Feature를 의미하며, Frequency는 Feature들 간의 차이를 의미한다.
여기서 Frequency가 적어야 그만큼 Feature간의 차이점이 없는 노드라는 것을 의미한다.
결국, Graph Fourier의 목표는 특정한 그래프의 관계가 Signal에 어느정도 포함되어 잇는지 알기 위함이다.
Laplacian Matrix
이번에는 Laplacian Matrix가 무엇일지 알아보자.
이유는, 위의 Fourier 변환 -> Filtering -> Inverse Fourier 변환(equation.3)가 Laplacian Matrix임을 증명해야하기 때문이다.
다음과 같이 D - A로 표현한 행렬이 Laplacian Matrix이다.
다른 수학식과 비교하면 안되는게 이는 두 행렬을 하나의 행렬로 합치는 것을 뜻한다.
Degree Matrix는 diag 행렬로 표현하였기에 저런 식으로 표현되었고, 그 행렬에 인접행렬을 빼서 맨오른쪽 행렬과 같은 표현이 되었다.
이 Laplacian Matrix을 어떻게 쓸까?
어떠한 노드의 Value를 가지는 벡터가 있다고 가정해보자. 이 Laplacian Matrix을 방금 언급한 벡터와 곱하게 되면 하나의 노드와 이웃 노드의 값 차이를 살펴볼 수 있게 된다.
Graph Fourier Transform with Laplacian Matrix
본 영상에서 깊게 다루지 않았고, 나도 잘 모르기때문에 결론부터 말하자면, 기존 Fourier Transform에도 Laplace Operator가 쓰이는 것과 대응관계이며, Laplacian의 고유벡터가 Fourier 기저 역할을 한다.
다시 이 수식으로 갔을때, 결국 U와 g 등을 사용해서 푸리에 변환하고 필터링 거치는 등의 과정의 결과물이 Laplacian Matrix라고 한다.
그리고 다음과 같은 특징을 가진다.
- 모든 고유값은 0보다 큼.
- Eigen-decomposition 의 diagonal entry가 0보다 크다.
- N개만큼의 고유값-벡터 쌍이 존재한다
영상에서는 친절하게 과정과 최종 결과물이 Graph Fourier Transform과 Laplacian Matrix이 관계가 있음을 그림으로 알려주었다.
그리고 Laplacian Matrix 적용 자체가 Convolution임을 의미한다. -> 뭐 그렇대요...
Polynomial Parametrization
본 논문은 푸리에 변환 및 필터링을 통한 Convolution 수식을 증명하였다. 하지만, 여기서 문제가 있는건 Filter이다.
두 가지의 문제점을 제시하였다.
- 모든 고유값을 다 사용함으로써 Localized 되지 않음 : Non-Parametric
- Eigen Decomposition으로 인한 연산 비용이 너무 크다.
따라서 Polynomial Parametrization을 g에 대해 유도하였다.
여기서, 고유값에 대한 Polynomial이 Laplacian에 대한 Polynomial로 변하였으며, k승에 따라 k-localized가 된다.
k가 1이면 노드와 거리가 1인 노드들에 대한 feature가 있음을 의미하고, k가 2이면, 노드와의 거리가 2임을 의미한다.
Chebyshev Polynomial
단순 Polynomial는 연산량이 여전히 많다는 문제점이 있기에 Chebyshev Polynomial를 도입하였다. 여기서는 재귀형태로 나타나면, k는 위와 같은 의미로 사용된다.
Layer-wise linear model
GCN은 위의 Chebyshev Polynomial의 k를 1로 두고 표현을 하였다.
유도한 수식은 아래와 같게 된다. L은 Fourier Transform을 표현할때 아래와 같은 표현식으로 나타냈다. 그 L을 대입한 결과가 우변을 뜻하게 된다.
Renormalization trick
GCN은 학습해야할 파라미터 theta가 두개가 있는 것보다는 하나의 thet로만 두고 학습을 진행해서 연산량을 줄이고자 하였다. 그래서 나온 결과는 다음과 같다.
하지만, 여기서 D와 A때문에 기울기 폭등 및 소실 문제가 발생한다고 하였다. 그래서 그 문제를 해결하고자 renormalization trick이라는 것을 제안하였다.
뭐, 대단한 것일줄 알았다만 D와 A에 I를 더해 자기 자신을 가리킬 수 있게끔 추가를 한 것뿐이다.
최종적으로, 유도된 식은 다음과 같다.
theta는 학습을 위한 filter 파라미터의 행렬을 뜻하고, 최종적인 output인 Z는 convolved signal matrix를 뜻하게 된다.
원래 O(n의 제곱)의 시간복잡도가 소요됐다고 치면(n은 파라미터 개수), ChebyShev Polynomials 적용 및 Renormalization trick 적용으로 인해 시간복잡도가 크게 줄어듦을 알 수 있었다.
본 논문에서 제안한 GCN의 실험은 2층 모델로만 진행하였다. 실험은 semi-supervised node classification on a graph로 Z를 다음과 같디 구성하였다.
위에서 증명한 수식에 의해 A는 위에서 수행해왔던 Convolution 연산을 의미하며, X는 input, W는 filter 파라미터를 의미하게 된다.
최종 출력을 위해 마지막 활성화함수는 softmax로 확률값을 출력되도록 하였고, 손실함수는 다중분류를 위해 cross-entropy를 사용하였다.
이후의 내용은 데이터셋에 관한 설명, baseline 모델, 위에서 filter 함수 유도과정에서 사용한 함수들과 최종 고안물인 renormalization trick을 사용한 filter 함수에 대한 실험이다.
많이 어려웠지만, GCN이 요즘 뜨는 세상에 탄탄하게 이해를 하고 넘어가야겠다는 결심 하나로 열심히 굴러보았다.
끝!