[딥러닝 홀로서기] Basic of Graph Convolutional Network

LEE HANBIN·2022년 10월 15일

Graph

목록 보기

1/2

1. What is Graph?

그래프란 무엇일까요? 그래프는 node(=vertex)와 이를 연결하는 edge로 이루어진 구조를 말합니다. 예를 들어볼까요? Molecular Graph는 node가 원자, edge는 원자 간의 화학 결합으로 표현되는 그래프 구조입니다. 이외에도 Social Graph, 3D Mesh를 그래프 구조로 표현할 수 있습니다.

그래프 구조를 분석하기 위해서 행렬로 그래프를 표현합니다. 그래프 노드의 개수가 N, 노드가 담고 있는 정보(=feature)의 개수가 F라고 합시다. 이 때, node 사이의 연결 관계를 표현하는 edge는 Adjacency matrix $A$ 로 표현할 수 있고, $N \times N$ 차원을 갖습니다.

아래 행렬 $A$ 는 예시 그래프의 Adjacency matrix 입니다.

$A=\begin{bmatrix}0&1&1&0&0\\1&0&1&1&1\\1&1&0&1&1\\0&1&1&0&1\\0&1&1&1&0\\ \end{bmatrix}$

$A_{ij}=1$ 는 $i$ 번째 node와 $j$ 번째 node가 edge로 연결되어있다는 것을 의미합니다. 반대로, $A_{ij}=0$ 은 두 노드가 서로 연결되어 있지 않음을 표현합니다. $A_{ij}$ 값이 1이나 0이 아닌 다른 실수 값으로 표현될 수도 있습니다. 이는 두 node 사이의 edge에 가중치를 부여한 것 입니다.

$A$ 의 대각선 성분이 0으로 표현되어있습니다. GCN에서는 이전 단계의 본인의 정보도 feature representation을 update하는데 사용하기 위해 대각 성분을 1로 표현합니다.

그래프의 node는 각각 정보를 갖고 있으며 이를 feature 라고 합니다. Node의 feature는 Feature matrix $X$ 로 표현할 수 있으며 $N \times F$ 차원을 갖습니다. 여기서 F는 feature의 개수를 의미합니다.

아래는 Feature matrix을 표현하는 행렬입니다.

$X=\begin{bmatrix}0&1&1&0&0&1\\1&0&1&1&1&0\\1&1&0&1&1&1\\0&1&1&0&1&1\\0&1&1&1&0&1\\ \end{bmatrix}$

2. Graph Convolution Network

2.1. Convolution Layer

GCN을 살펴보기에 앞서 Convolution layer에 대해 살펴보겠습니다. Convolution layer은 input에 filter을 slide 하며 feature을 추출합니다. Fully Connected Layer와는 다르게 feature을 추출할 때 가중치를 공유(weight sharing)을 하기 때문에 아래와 같은 장점들이 있습니다.

Parameter 수 감소 $\rightarrow$ overfitting을 방지, 연산 비용 감소
특정 feature의 주변 feature로부터 학습 (receptive field)
이미지에 변환(미세한 회전) 에 강인

CNN을 통과하면서 각 layer의 activation map이 업데이트 됩니다. 이러한 activation map은 이미지의 특성을 결정하는 feature들을 말합니다. GCN에서는 CNN을 어떻게 응용했을까요?

2.2. GCN

2.2.1. Graph Convolutional Layer

GCN은 어떤 node와 edge로 연결된 주변 node의 정보를 활용하여 node feature를 업데이트 합니다. 위 그림을 다음과 같은 식으로 표현할 수 있습니다.

$H^{(l+1)}_1=\sigma(H^{(l)}_1W^{(l)}+H^{(l)}_2W^{(l)}+H^{(l)}_3W^{(l)}+H^{(l)}_4W^{(l)}+b^{(l)})$

$l$ 은 l번째 layer을 나타냅니다. $H^{(l)}_1$ 은 l번째 layer에서 hidden state(=node feature matrix), $W^{(ㅣ)}$ 는 $l$ 번째 layer의 weight, $b^{(l)}$ 는 bias, $\sigma$ 는 activation function을 의미합니다.

위 식을 일반화하면 아래와 같습니다.

$H^{(l+1)}_i=\sigma(\Sigma_{j \in N(i)}H^{(l)}_jW^{(l)}+b^{(l)})$
$~~~~~~~~~~~=\sigma(AH^{(l)}W^{(l)}+b^{(l)})$

수식을 보면 알 수 있듯이 GCN 또한 CNN과 마찬가지로 가중치( $W$ , $b$ )를 공유합니다. $\Sigma_{j \in N(i)}H^{(l)}_jW^{(l)}$ 이 $AH^{(l)}W^{(l)}$ 으로 표현되는 간단한 행렬 연산으로 변환되었는데 어떻게 가능한걸까요? $A$ 는 Adjacency matrix라고 앞에서 정의했습니다. $A$ 에서 edge로 연결된 node는 1, 연결되어있지 않은 node는 0으로 나타나기 때문에 행렬 연산을 통해 이웃 노드의 정보만을 활용하여 hidden state을 업데이트 할 수 있습니다.

2.2.2. Readout - Permutation Invariance

같은 그래프일지라도 node의 번호가 다르면 adjacency matrix $A$ 와 feature matrix $X$ 가 다르게 표현됩니다. Node-wise summation은 hidden state를 MLP(multi-layer perceptron)에 통과시키며, 이를 통해 matrix 표현이 달라도 같은 그래프 정보를 표현하도록 할 수 있다는 것이 수학적으로 증명되었습니다.

2.2.3. Overall Structure of GCN

GCN은 Graph Convolutional layer을 활용하여 주변 node로부터 hidden state를 업데이트 합니다. Readout을 통해 Graph를 펴고, Predictor로 label을 예측합니다.

3. Advanced Techniques of GCN

마지막으로 GCN 성능을 향상시키기 위한 다양한 테크닉을 살펴보겠습니다.

3.1. Inception

CNN에는 다양한 사이즈의 filter을 사용하여 feature을 추출하는 아이디어가 있습니다. 이를 통해, 보다 다양한 관점에서 feature를 분석할 수 있는데 이 아이디어를 GCN에서도 채용할 수 있습니다.

Graph Convolution layer를 여러번 통과하면 이웃의 이웃 node의 정보까지 활용하여 feature를 update 할 수 있습니다. feature을 업데이트 할 때 사용되는 이웃 수에 따라서 feature의 흐름을 다르게 하여 다양한 관점에서 feature을 추출할 수 있습니다.

3.2. Skip Connection

Skip Connection은 ResNet에서 나온 아이디어로 $F'(x)=x+F(x)$ 으로 표현할 수 있습니다. Layer을 통과하기 전의 feature와 통과한 후의 feature을 모두 사용하여 vanishing gradient 문제를 방지하고, 이전의 정보를 활용할 수 있게 합니다.