[논문 리뷰] Graph Convolutional Network (GCN)

오늘은 Graph Convolutional Network에 대해 소개하겠습니다. 우리 살아가는 인간관계처럼 우리 주변에는 수많은 그래프가 있고 그것을 잘 이해하기 위한 획기적인 모델입니다. 본 글은 Semi-Supervised Classification with Graph Convolutional Network 논문을 바탕으로 설명하는 글입니다.

Graph Neural Network 구조

Introduction

우리가 다루는 많은 정보는 graph의 형태로 이해할 수 있는데, 이 구조를 기존의 Convolution 또는 Recurrent Model로는 제대로 다루기 어렵습니다. 그 이유는 크게 세가지가 있는데,

1. 격자(grid) 구조로 그래프를 다룰 수 없다. 그래프란 이미지나 다른 데이터와는 달리 그 구조적인 형태가 매우 자유롭다
2. 서로 다른 두 node의 관계를 보다 풍부하게 표현할 필요가 있다.
3. 그래프 내에는 여러 가지 성질을 가진 entity가 있어 이들을 동등하게 고려하는 것은 불공평하다.

때문에 우리는 그래프를 그래프답게 다뤄야 하는데, 이 논문이 그 중에 가장 유명합니다. 그 이유는 Convolution의 개념을 그래프에 도입하여 우수한 성능을 보여줬기 때문입니다.

이 논문이 주목 받은 이유는 아래의 두가지 이유가 주요한데,

1. Node-level Semi-supervised Learning
   우리가 가지고 있는 그래프에는 모든 node가 레이블링 되어 있지는 않다 (몇개는 되어있고, 몇개는 안되어있다). 그렇다면 우리가 알고 있는 node를 활용하여 정체를 모르는 node들을 맞출 수 있을까??
2. Graph Convolutional Network
   기존 많은 딥러닝 연구에서 큰 성공을 거둔 convolution-based 방법을 그래프에도 도입시킬 수 있지 않을까??
   (결과적으로 First-order approximation of spectral graph convolution이라는 방법으로 graph에 convolution을 성공적으로 도입)
   

이제 차근차근 알아보겠습니다.

---

Graph Convolution의 의미

신호처리 문제에서 convolution은 두 신호 \(f\)와 \(g\)에 대해 \(f*g\)로 표현하며, 이것은 \(f\)가 \(g\)에 의해 어떻게 변형되는가를 나타냅니다. 이것은 두 신호의 integral로 해석할 수도 있기 때문에 만약 어떤 지점에서 결과값이 크다면 해당 지점에서의 두 신호는 서로 큰 양의 상관관계를 갖는다고 해석 가능합니다. (정확히는 \(f\) 또는 \(g\) 한쪽은 inverse되어 계산되지만...)
아무튼 두 데이터 간의 상관관계를 파악하는데 참 좋은 방법이 convolution입니다.

그래프에 convolution을 적용한다는 말은, 그게 가능하다면 임의의 두 node 사이의 관계의 정도를 파악하는데 매우 효과적이라고 예상할 수 있겠죠?
정리하자면 그래프 내의 임의의 node 사이의 관계를 추론함으로써, 정체를 알고 있는 node를 활용하여 정체를 모르는 node들을 알아내는 것이 이 논문의 목적입니다. 참고로 기존에 Graph Laplacian을 활용한 Graph Smoothing을 했던 연구가 있었습니다 (그 목적은 똑같이 Semi-supervised 입니다).

---

Method

이제 Graph Convolution이 대체 무슨 의미인가 겉핥기로 알아봤으니 이것을 어떻게 할 수 있는가 살펴보겠습니다 (이 블로그에 너무도 자세히 설명되어 있으니 참고하자).

$$ H^{(l+1)} = \sigma \left( \widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)} \right) $$

이게 그래프에서 Convolution을 수행하는 방식이고 변수는

• \(X\): Node feature (각 노드의 상태를 나타내는 것)
• \(A\): 인접 행렬 (Adjacency feature, 각 노드 간의 연결을 나타내는 것)
• \(H^{(l)}\): \(l\)번째 layer의 hidden state입니다. 참고로 \(H^{(0)} = X\), 즉 Initial node feature입니다.
• \(\widetilde{A}\): \(A + \mathit{I}_{N}\). 인접 행렬에 자기자신(노드)에의 연결을 추가한 행렬입니다.
• \(\widetilde{D}\): \(\widetilde{D}_{ii} = \sum_{j}\widetilde{A}_{ij}\). 이건 각 노드의 degree. 즉 다른 노드와 얼마나 강하게 연결되어 있는가를 나타냅니다.
• \(W^{(l)}\): \(l\)번째 layer의 learnable parameter입니다. 결론적으로 이걸 학습하는 것.
• \(\sigma\): Activation Function

이것은 사실 그래프 내에서 각 노드 간의 convolution을 수행하는 과정에서 얻을 수 있는 결론입니다.

사실은 Spectral Convolution을 수행하고, 그것이 너무나 많은 연산량 \(O\left (\mathit{N}^{2} \right)\)을 요구하기 때문에 Chebyshev polynomials에서 1차항까지만 살리는 근사를 수행합니다. 아무튼 과정은 논문에도 나와있고, 제 다른 블로그에서도 설명하고 있기 때문에 넘어가겠습니다.

---

Experiments

실험에서는 여러 데이터셋에 대해 Semi-supervised Learning을 수행했습니다. 다시금 말하지만 이것은 '정체를 아는 일부의 노드를 통해 정체를 모르는 노드의 정체를 까발리는 것'입니다.

주변에 정체를 아는 노드를 통해 모르는 친구들을 알아보자!

제가 그린 그림에서는 정체를 아는 노드가 참 많지만 실험에서는 아주 일부 노드의 정체를 알고 있습니다. 그리고 나머지의 정체를 추론해야 하는 난이도가 사악한 과제입니다.

각 데이터셋 종류 및 노드, 엣지 갯수를 포함한 정보. Label rate는 0.001이라면 전체 노드의 0.1%만 supervised이고 나머지 99.9%는 모두 예측해야 한다는 뜻

---

GCN의 결과는 실험한 모든 데이터셋에 대해 기존 모델들을 상회했습니다. 숫자를 잘 보면 예를 들어 Citeseer 데이터셋에 대해 ICA와 비등한 수준을 보였지만 ICA는 NELL 데이터셋에 대해 어마어마한 차이를 보이는 등 기존에는 모든 데이터셋에 대해 우수한 성능을 보인 모델이 없었습니다.

하지만 GCN은 모든 데이터셋에 대해 전에 없던 우수한 성능을 거둠으로써 Graph 구조의 이해에 GCN이 정말 효과적임을 보였습니다.