Introduction

GCN(Graph Convolution Network)에 대하여 개인적으로 공부한 부분을 토대로 기술합니다.
GCN을 이해하기 위한 기초적인 개념부터, G / C / N 각각이 무엇을 뜻하는지 학습합니다.

이번 파트에서는 GCN에서 C에 대하여 학습해 보도록 하겠습니다.
G에 관해서는 이전 PART.01 Graph를 참고해주세요.

Convolution

자 짧게 컨볼루션에 대해서 알아보도록 합시다. CNN 및 영상처리때 자주 봤었던 연산이죠.
자세하게 설명된 곳이 다양하고 많으니, 우리는 GCN에서의 컨볼루션을 중점으로 가져가보도록 하겠습니다.

컨볼루션이란 쉽게 말해 필터(Kernel)를 shift시켜가며, dot product연산을 수행하는 것을 말합니다.
※ 여기서의 dot product는 행렬곱이 아니라 성분끼리 곱하는 곱셈(element-wise multiplication)입니다.

Stride 값에 따라 필터링을 적용할 때의 이동이 한칸씩이 아닌 여러 칸으로 이동될 수 있고, 이러한 컨볼루션 연산을 수행하게 되면 그림과 같이 영상의 크기가 줄어들게 됩니다. 이러한 영상의 크기를 줄어드는 것을 방지하기 위해 입력영상의 외각에 0을 채우는 제로 패딩을 하기도 하죠.

Convolution 예시

32x32, depth가 3 (32x32x3)인 이미지가 있고, 5x5x3 크기의 필터를 사용하여 컨볼루션 연산을 수행한다고 가정해 보겠습니다.

컨볼루션 연산에서 컨볼루션 필터의 채널의 수는 입력값의 채널 개수와 동일하므로 3이 됩니다.

이러한 입력 영상에 하나의 5x5x3 필터를 적용하여 연산을 쭉 이어나가게 되면 다음과 같이 하나의 activation map이 만들어집니다.

이러한 적용한 필터의 수 에따라 feature map(파랑, 초록)이 생성되게 됩니다.

※그림의 activation map은 feature map에 활성함수를 적용한 결과.

이 연산이 또다른 필터에 대해서 적용되면 새로운 연산이 이루어지게 되고 dept 1짜리 새로운 activation map이 생성되게 됩니다.

Convolution 연산의 특징과 이점

이러한 Convolution 연산의 특징은 무엇일까요?

• 적은 수의 파라미터 (계산량이 적고, 오버 피팅의 위험이 낮음)
• 지역적인 특성을 학습가능

컨볼루션 연산은 너무 자세하게까지 연산되는 fully connected 방식보다, 필터를 적용하여 특징으로 분류하므로 파라미터가 적어 계산량이 적고 과적합되는 Overfitting의 위험성도 낮출 수 있습니다.
또한 앞의 5x5x3 필터와 같이 해당 영역의 지역적인 부분을 학습하므로 지역적인 특성을 반영할 수 있습니다.

한마디로 표현하자면..

➡ Image에 대해 주로 사용하는 Convolution연산을 Graph에 대해 적용한 것이 GCN 입니다.

CNN과 GCN의 비교

CNN과 GCN의 차이는 무엇일까요?

• conv : 컨볼루션 연산

CNN

CNN의 경우 이미지가 주어졌을 때, conv, pooling 레이어를 반복하며 feature extraction(특징추출)을 수행하는 부분과 flatten, fully connected layer를 통해 classification(분류)을 하는 과정으로 나뉘게 됩니다.

각각의 레이어를 거치면서 Convolution 연산을 수행하며, 커널을 학습(업데이트)하게 되죠.

GCN

GCN은 각 레이어를 거치며 Convolution 연산을 수행하고 Graph 값을 업데이트 합니다.

근데 그래프는 vertex와 edge의 구성인데, 그렇다면 그래프를 업데이트 한다는 것은 무엇을 업데이트 하는 것 일까요?

➡ 바로 그래프에서 정보를 결정하는 것은 노드에 담긴 정보. 즉 노드의 feature값들이 업데이트 되는 것입니다.

Graph Structure

추가적인 설명을 위해 잠깐 GCN 그래프의 구조를 다시한번 보고 넘어가도록 하겠습니다.
해당 구조에 관한 설명은 이전 PART.01 Graph에서도 설명했었습니다.

예를 들어 왼쪽에 4개의 노드로 이루어진 그래프가 있고, 각 노드는 5개의 feature를 가진다고 가정 합시다.

쉽게 이미지의 픽셀이라고 생각한다면, r/g/b, transparency(투명도), bright(밝기)값이 되겠죠.

Adjacency matrix

adjacency matrix는 연결성을 나타내므로 오른쪽과 같이 노드 상호간의 연결성이 0, 1로 나타납니다.

※ PART.01에서 본 adjacency matrix와는 달리 자기 자신과의 연결성인 대각선 방향이 전부 1로 표현되어 있는데, 여러 논문에서 일반적으로 adjacency matrix $A$에 단위행렬 $I$를 더한 형태로 사용하는 것이 일반적이라고 합니다.

Feature matrix

Feature matrix는 이러한 노드 개수 4개, featur 개수 5개로 4x5 크기의 매트릭스가 나오게 됩니다.

※ 각 노드의 특성별로 그림에서 색을 약간씩 다르게하여, 위 이미지와 같이 표현했다고 보시면 됩니다.

GCN에서의 Convolution

앞서, Convolution 연산의 특징(장점)에 대해 알아보았습니다.
자 그럼 GCN에서 Convolution 연산을 왜 사용하는 것일까요?

GCN은 위 그림과 같이 이전 레이어 다음 레이어로 넘어가면서 노드의 feature 값을 업데이트하게 됩니다.

이때 사용되는 컨볼루션 연산은, 사실상 CNN에 사용하던 컨볼루션 연산을 그대로 그래프에 적용한 것이죠.
즉, CNN에서의 이점이 되는 컨볼루션 연산의 특성을, 그래프에도 적용한 것 입니다.

그러한 연산의 특성이 바로 Weight Sharing과 Learn Local Features입니다.

이러한 특성을 사용해서 지역적이고, 적은 연산량으로 노드의 feature 값을 업데이트하게 되죠.

Weight sharing

Weight sharing이란 무엇일까요?

Weight sharing이란, Fully connected 구조와는 다르게 Convolution의 구조에서 나타나는 특징으로,
말 그대로 가중치를 공유한다는 개념입니다.

그럼 이것이 어떻게 이루어 질까요?

위 그림의 예시를 통해 비교하며 살펴 보도록 하겠습니다.
S는 업데이트가 수행된 이후의 결과, X는 업데이트 전의 값이라고 생각하시면 됩니다.

Fully connected 구조

자 왼쪽 Fully connected 구조부터 살펴 봅시다.

결과 $s_1$ ~ $s_5$을 결정하기 위해서 $x_1$ ~ $x_5$의 입력값이 전부 사용되고, 전부 각각 다른 가중치($w$)들이 사용되고 있습니다.

이렇게 된다면, 각 노드마다의 가중치가 제각각 다르게 필요하니 연산량 또한 증가하고, 이러한 가중치를 저장 해야하는 공간적인 부분에서도 부담이 됩니다.

Convolution 구조

반면 오른쪽 Convolution의 구조를 봅시다.

식을 보면 $s_1$ ~ $s_5$의 출력 값을 내기 위해서 인접한 입력 값에 항상 동일한 가중치가 사용되는 것을 볼 수 있습니다.
($w_{11}, w_{12}, w_{13}$)

이것이 바로 weight sharing입니다.

하나의 커널을 통해 입력데이터 전체에 동일한 가중치를 적용하는 것이죠.
(※ 얇은 화살표 3개가 한세트로, 이를 하나의 커널로 생각하면 됩니다.)

이를 통해 가중치(뉴런, 화살표)의 수를 줄일 수 있고, 시/공간적 이점을 살릴 수 있습니다.

Learn local feature

두번째 특성은 Learn local feature 입니다.

일반적인 MLP의 경우 hidden layer의 노드들이 모든 input노드와 fullyconncted되어 있기에 과적합의 문제나, 연산량의 측면에서 이점을 보기가 어렵습니다.
하지만 CNN에서는 filte가 이동하므로 local featur들이랑만 연산하고 activation map을 생성하므로 각 activation map의 pixel들은 global한 전체 feature들이 아닌 특정한 지역의 local feature들에 의해서만 학습된다고 할 수 있습니다.
(또한 층이 깊어질수록 해당 뉴런이 담당하는 receptive field또한 더 넓어지게 됩니다.)

Next

정리하자면..

CNN은 Weight Sharing과 Learn Local Features의 특성을 통해 생성되는 activation map의 각 픽셀 상관 관계를 높일 수 있습니다. 결과적으로 연산량도 줄이고, 오버피팅의 문제또한 어느정도 해결하며, 근처 pixel끼리의 상관 관계가 높은 input data를 더 잘 학습할 수 있는 것이죠.

이러한 CNN의 컨볼루션 연산에서의 특성을 Graph에 적용하는 것이 바로 GCN이라고 할 수 있겠습니다.

다음으로는 GCN에서의 컨볼루션 연산의 절차 및 과정에 대해서 다뤄보도록 하겠습니다.