[GCN] Graph Convolutional Networks 논문 리뷰

GCN.pdf

0.83MB

 

목적:

어떤 그래프 구조가 있다고 생각해 보자. 우리는 모든 노드들의 라벨을 채워 넣고 싶어 한다. 하지만 라벨이 채워져 있는 노드가 몇 개 없다면? 가령 그 비율이 전체 노드 개수의 5% 뿐이라면? 어떻게 나머지 라벨이 없는 노드들의 라벨을 예측할 것인가에 대한 연구가 Graph Convolution Network이다. 즉 적은 수의 label known 노드를 가지고 unknown 노드들을 classification 할 수 있는 알고리즘이다. 적용 범위는 소셜 네트워크, 논문의 인용 그래프 등에서 사용 가능하다.

 

문제:

라벨이 있는 노드들만 가지고 지도 학습을 수행하기에는 정보가 너무 부족하다. 예를 들어 전체 노드의 5%만 라벨이 있다면 각 노드의 피쳐를 학습시켜 라벨을 예측하는 모델은 과연 나머지 95%의 노드들에 적합한 예측을 내놓을 수 있을까? 나머지 노드들의 정보도 적정히 학습에 포함시킬 수 있는 방법이 뭐가 있을까? 이로써 이 문제는 라벨이 있는 노드와 없는 노드 모두 학습에 포함시킴으로 준지도 학습(semi-supervised learning) 임을 알 수 있다.

 

해결:

우선 classification 문제에 초점을 두며 국소적(local) 그래프 구조와 노드들의 피쳐를 학습할 수 있게끔 은닉층을 학습시킨다. 그래프에 존재하는 모든 노드 X와 인접 행렬 A를 사용하여 그래프 구조를 NN에 인코딩하고 라벨이 있는 노드를 통해 학습시킨다. Local 구조는 특정 노드의 1 hop 간격을 관찰하면서 spatial 한 노드를 spectral space로 옮겨 convolution을 수행하고 다시 spatial로 Fourier Transform 하여 local 한 특징을 추출할 수 있다. 이 과정에서 노드의 피쳐는 자연스럽게 연산에 포함이 되어 학습의 대상이 된다. 이 과정을 2개의 은닉층을 가지는 인공신경망으로 최적화해준다.

 

Why convolution?

 

왜 그래프에 컨볼루션을 사용할까? 이를 이해하려면 논문 초기에 소개되는 라플라시안 regularization의 한계에 대해 살펴볼 필요가 있다.

여기서 $A_{ij}$는 인접행렬의 i번째 행, j번째 열을 뜻한다. 즉 i노드와 j노드가 연결되어 있으면 1, 그렇지 않으면 0이다. $L_{0}$은 라벨이 있는 노드들로 학습된 손실이고 $L_{reg}$는 라벨이 없는 노드들 중에서도 연결되어 있는 노드에 한해서만 손실을 계산한다. 여기서 유심히 봐야 할 것은 결국 목적 함수 f는 노드 인풋을 받으면 class에 대한 확률을 벡터 형태로 반환할 것이며 "i노드($X_i$)와 j노드 ($X_j$)가 이웃이라면 class 확률 벡터의 차이가 작아야(같은 라벨로 예측해야) 손실이 작다"라고 가정하고 있다. 하지만 일대일 연결성만이 노드 간의 노드 판별 조건이 되어버린다. 이 모델은 연결성에만 국한해서 정확한 분류를 위한 다채로운 그래프의 특성을 무시하는 격이 된다.

 

그래서 노드와 노드 간 일대일로 비교하는(두 노드의 class 이외에는 아무 관심이 없다...) 것이 아닌 그 노드 주변의 환경까지 포착하여 유의미한 특징을 끌어낼 수 있는 컨볼루션을 그래프에 적용시키는 것이다.

 

하지만 문제가 있다. 컨벌루션을 어떻게 그래프에 적용할까?

 

일반 픽셀 이미지에서는 고정된 크기의 필터를 통해 고정된 크기의 픽셀들만 컨볼루션 하면 그만이었다. 하지만 그래프에서는 이웃의 숫자가 노드마다 재각각이다. 예시를 하나 살펴보자.

 

주황색 테두리를 갖고 있는 필터의 값과 거기에 걸쳐 있는 기존 행렬의 값이 곱하고 더해져서 새로운 값을 도출해 낼 수 있다. 인접한 픽셀들은 서로 연관되어 있을 가능성이 크다는 가정을 이용한 결과이다. 이것이 의미하는 것은 본인 포함 주변 8개의 픽셀들이 인접해 있기 때문에 컨볼루션을 계산했을 때 합산된 픽셀로 유의미한 정보가 저장됨을 뜻한다. 

 

또한 여기에서 라플라시안 regularization이 왜 전체적인 구조를 고려해야 할 때 별로인지 이유를 알 수 있다. 예를 들어 28*28 크기의 픽셀 이미지가 있다고 가정하자. 이것을 다층 퍼셉트론 인공 신경망으로 학습시키려면 이 픽셀 이미지를 784*1짜리 벡터로 찌부시켜야 한다. 하지만 이렇게 압축된 이미지는 공간적 특성을 완전히 상실해버리고 만다. 픽셀 하나하나만 관찰해서 이 이미지가 무엇인지 알 수 있는가? 없다. 마찬가지로 노드를 하나하나만 관찰해서는 그래프의 classification perspective에서의 구조를 읽어내기 힘들다. 따라서 공간적 특성을 살려 이미지를 학습시키고 싶은 방법이 CNN이다.  

 

GCN도 마찬가지이다. 그래프에서 국소적인 공간을 관찰하여 공간적 특성(노드의 연결성)을 살려 학습하는 방법을 CNN에서 motive로 갖고 온다. 인접해 있는 노드들끼리의 비슷한 특성이 존재할 것이라는 가정에서 출발하는 것이다. 그래서 노드 간의 연결을 유연하게 처리해 주는 행렬이 인접행렬(A)이다. 하지만 위의 이미지 컨볼루션에서도 알 수 있듯이 기준 픽셀(예시 그림에서는 3행 4열에 해당하는 픽셀)도 연산에 포함시킨다. 즉 GCN에서도 중심 노드와 그 이웃들을 전부 연산에 포함시켜야 한다. 그래서 $\tilde{A} = A + I_N$으로 self connection을 추가한다. 위의 경우에는 격자 그리드에서 컨볼루션을 수행하기 쉽지만(그냥 이미지 전체를 필터로 쓸어가면서 곱하고 더하고 그 결과를 저장해 주면 된다). 그래서 고안된 방법이 그래프의 경우 노드 1개를 신호의 관점으로 해석하는 것이다. 

 

 

우리가 layer 학습에서 사용할 수식이다.

$H_{}^{(l+1)}$ : NN의 $l+1$번째 층

$H_{}^{(l)}$ : NN의 $l$번째 층

$W_{}^{(l)}$ : NN의 $l$번째 가중치 행렬

$\tilde{A}$ : self loop를 추가한 인접 행렬

$\tilde{D}$ : $\tilde{A}$로 얻은 degree matrix

$\sigma$ : 활성화 함수(ReLu)

 

이 수식이 나오게 된 이론적 배경에 대해 알아보자.

 

먼저 우리는 CNN을 모방하려면 그래프의 국소 지역과 필터를 컨볼루션 할 줄 알아야 한다. 여기서 국소 지역이란 기준 노드 1개를 기준으로 1 hop거리의 이웃 노드들이고 필터는 크기가 N*N인 대각 행렬로 정의된다.

$$g_\theta=diag(\theta)$$    $$\theta=\mathbb{R}^N$$

CNN에서 필터값은 레이어 깊이가 깊어져도 바뀌지 않아 파라미터를 재사용하여 계산을 아낄 수 있다는 장점이 있다. 이와 마찬가지로 $g_\theta$필터는 하나만 global 하게 사용한다. 

 

먼저 노드 1개와 필터($g_\theta$. 여기서 $g$는 $\theta$벡터로 파라미터화된 대각선 행렬이다. $g_\theta=diag(\theta)$. 이때 필터는 eigen values의 함수이므로 이미 spectral domain에 있음을 잊지 말자)의 컨볼루션부터 정의해 보자. 자 이제 필터와 노드 $x$가 있다고 가정하자. 이 둘을 컨볼루션 연산을 하려면 

다음과 같은 식이 연산되어야 한다. 

 

여기서 $U$는 라플라시안 행렬($L=D-A$)을 eigen decomposition 하여 얻은 모든 eigen vector를 행렬 형태로 나타낸 것이다.

 

$U$는 독특한 properties 덕분에 매우 유용하게 사용된다.

1. $UU^T=I_N$

2. 어떤 spatial domain의 벡터 $x$를 spectral domain으로 옮기면 $U^Tx$이다. 그 반대 과정을 거치고 싶으면 $U$를 곱하면 된다.

3. 모든 eigen vector들은 orthonormal 하다. 

 

푸리에 변환에 의해서 spatial domain에서의 컨볼루션은 spectral domain에서의 곱이다. 즉 아래와 같이 위의 컨볼루션이 유도된다. 

$x$와 $g_\theta$를 spectral domain으로 옮기려면 각각 $U^Tx$를 곱한 상태로 서로 곱해준다.

 

결국 행렬의 결합 법칙 덕분에 이와 같이 표현될 수 있다.

$U(g_\theta (U^Tx))=Ug_\theta U^Tx $

spatial domain에서의 컨볼루션 -> spectral domain에서의 곱 -> 다시 spatial domain 으로의 변환

 

하지만 문제가 있다. $U$ 행렬마저 N*N크기라서 계산에 큰 부담을 준다. 또한 eigen docomposition 자체의 연산 자체도 버겁다.

 

이때 Chebyshev Polynomial을 이용하면

위와 같이 근사가 가능하다. 위의 표현은 K-th order laplacian이므로 그래프에서 중심 노드로부터 K steps만큼 깊게 들어감을 알 수 있다. 

 

K=1로 설정하고 여러 가정들을 덧붙이면 아래의 최종 수식이 나온다.

방금 전에 K=1이라고 가정하였기 때문에 GCN은 중심 노드를 기점으로 이웃 노드들만 학습의 대상으로 삼는다(regularized adjacency matrix에 의해 이웃 노드들만 학습에 포함된다). 즉 hidden layer이 2개임을 알 수 있다. 

 Z는 라벨들의 확률적 최종 결과를 의미한다.

 C는 피쳐의 개수, F는 필터의 개수(예측하는 라벨의 개수)를 나타낸다. $X_1, X_2, X_3, X_4$는 개별 노드의 피쳐를 나타낸다(노드 하나당 피쳐는 3개임을 유추할 수 있음). 마찬가지로 $Z_1, Z_2, Z_3, Z_4$는 라벨 하나당 해당하는 확률(softmax로 구해짐)을 나타낸다(총 classify 가능한 라벨이 5개임을 알 수 있음). 즉 그림에서 알 수 있듯이 피쳐가 각각 필터(가중치)를 동반한 신경망 안으로 학습되고 그 결과로 $Z$가 나오고 앞에서 언급했듯이 손실 함수는 라벨이 있는 노드만 가지고 진행된다. 즉 1번 노드와 4번 노드만 라벨을 갖고 있음을 알 수 있다. 

이후에 크로스 엔트로피로 손실 함수를 계산해 주면 끝이다. 여기서 $Y_L$은 라벨이 있는 노드들의 indices를 의미한다. 즉 라벨이 있는 노드($Y_{l}$)와 예측 노드($Z_{l}$)를 크로스 엔트로피 해준다.

위 이미지는 5%의 known label 데이터만 갖고 GCN을 적용하여 학습한 결과이다. 자세히 보면 얼추 군집을 생성함과 동시에 분산되게 class가 퍼져 있음을 알 수 있다. 만약 laplacian regularization을 사용했다면 known label들을 기점으로 clustering 되었을 확률이 매우 크다.