Graph Neural Network

GNN , graph-theory , neural-network , GCN

Graph Neural Network

GNN (Graph Neural Network)는 그래프 구조에서 사용하는 인공 신경망을 말합니다. 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 CNN (Convolutional Neural network)나 RNN (Recurrent Neural network)가 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어지는데 반해서 GNN의 경우에는 input이 그래프 구조라는 특징이 있습니다. 이 글에서는 GNN의 기본 원리와 GNN의 대표적인 예시들에 대해서 다루도록 하겠습니다.

Neighborhoods Aggregation

GNN은 입력으로 그래프 구조와 각 노드별 feature 정보를 받습니다. 입력으로 받은 feature 정보와 그래프 내에서 나타나는 이웃 정보를 바탕으로 각 노드 별 vector embedding을 출력 결과로 얻어냅니다. GNN의 하나의 레이어에서 각 노드들은 그래프 상의 이웃들의 정보와 자기 자신의 정보를 이용해 embedding을 만듭니다. 예를 들어, 이웃으로 노드 B, C, D를 갖는 노드 A가 있고, GNN이 layer 하나로 이루어져 있는 경우를 생각해봅시다. 이러한 경우에 A의 embedding은 A의 feature와 함께 B, C, D의 feature에 의해서 결정됩니다. CNN에서 인접한 셀의 정보를 함께 사용하는 필터가 있는 것처럼, GNN에서는 인접한 노드들의 정보를 함께 사용하는 구조가 있다고 생각할 수 있습니다.

이러한 레이어를 여러 개 쌓으면 딥러닝을 할 수 있습니다. 레이어를 두 개 쌓았다고 생각하고 그래프 구조는 이전의 예시와 동일하다고 해봅시다. 이 경우에는 두 레이어를 모두 거친 A의 embedding은 B, C, D, 그리고 A의 첫 번째 레이어를 거친 후의 embedding에 의해서 결정됩니다.

그렇다면 GNN에서는 어떻게 자기 자신의 정보와 이웃들의 정보를 합쳐서 embedding을 구할까요? 대부분의 GNN은 먼저 이웃들의 정보를 모으고, 모은 정보를 통해 얻은 새로운 값과 이전 상태의 자기 자신의 값을 이용하여 새로운 embedding을 얻어냅니다.

$h_{v}^{k}$를 $k$번째 레이어를 거친 후 노드 $v$의 embedding이라고 합시다. 그렇다면 $h_{v}^{k}$를 구하는 알고리즘은 다음과 같이 나타낼 수 있습니다.

for v in V:
	h_{v}^{0} = (v의 feature vector)
for i in range(1, k+1):
	for v in V:
        a = AGGREGATE({h_{u}^{i-1} | {u, v} in E})
        h_{v}^{i} = CONCAT(h_{v}^{i-1}, a)

GNN Training 및 활용

앞에서는 GNN에서 중요한 개념인 Neighborhood aggregation에 대해서 다뤘습니다. 그러므로 이제 AGGREGATE와 CONCAT 함수만 알고 있다면 각 노드별로 embedding을 구할 수 있을 것입니다. 여기서는 AGGREGATE와 CONCAT 함수를 어떻게 학습하는지에 대해 알아보겠습니다.

일반적인 인공 신경망에서의 학습하는 과정은 다음과 같습니다.

학습할 인공 신경망의 구조를 정하고, input을 준비한다.
loss function을 정의하고, 어떤 optimizer를 사용할지 결정한다.
2번에서 정의한 loss function과 optimizer를 사용하여 loss가 0에 가까워지도록 신경망의 parameter를 학습한다.

GNN을 학습하는 과정도 위의 학습과정과 동일합니다.

AGGREGATE, CONCAT 함수를 정의하고, input으로 사용할 그래프를 준비한다.
loss function을 정의하고, 어떤 optimizer를 사용할지 결정한다.
loss가 0에 가까워지도록 신경망의 AGGREGATE, CONCAT 함수의 parameter를 학습한다.

optimizer는 RMSProp이나 Adam 등 일반적인 인공 신경망에서 널리 사용되는 optimizer를 그대로 사용할 수 있습니다. loss function을 정의하는 방법은 GNN을 사용하여 어떠한 문제를 풀고싶은가에 따라서 달라집니다.

첫 번째로, Node classification 문제에 GNN을 활용할 수 있습니다. supervised learning을 하는 경우에는 각 노드가 어떤 class에 속하는지에 대한 학습 데이터가 주어질 것입니다. 이러한 경우에 학습하는 방법은 일반적인 classification 문제를 푸는 것과 동일합니다. 예를 들어, loss function으로 cross entropy loss를 사용할 수 있습니다. 그래프 하나에 있는 모든 노드들을 batch로 학습한다고 생각하면 됩니다.

문자열의 각 단어의 embedding을 구하는 Word2Vec처럼 Unsupervised Learning을 사용하여 그래프 구조를 고려한 각 노드의 embedding을 구할 수 있습니다. 예를 들어서, logistic regression을 사용해서 loss function을 다음과 같이 나타낼 수 있습니다.

$L$ = $\sum_{{u, v} \in E} log(\sigma (h_{u}^{T}h_{v})) + \sum_{{u, v} \not\in E} log(1 - \sigma(h_{u}^{T}h_{v}))$

위의 loss function에서 두 노드가 연결되었을 때 cosine similarity가 1이고, 그렇지 않을 때 cosine similarity가 0이면 loss가 0으로 최소가 됩니다. $\sigma$는 공역이 (0, 1)에 속하는 activation function을 의미합니다. 대표적인 예시로는 sigmoid function이 있습니다.

GNN과 관련된 아이디어들

간단한 아이디어

가장 간단한 아이디어로, AGGREGATE 함수의 결과를 이웃들의 이전 단계 embedding의 평균이 되도록 정의할 수 있습니다. 이 경우, $h_{v}^{k}$는 다음과 같이 나타낼 수 있습니다.

$h_{v}^{0}$ = ($v$의 초기 feature)

$h_{v}^{k}$ = $ \sigma (W_{k} \sum_{{u \vert {u, v} \in E}} \frac{h_{u}^{k-1}}{\vert {u \vert {u, v} \in E} \vert} + B_{k}h_{v}^{k-1}) $

위의 식에서 각각의 $k$에 대해서 $W_k$와 $B_k$가 학습 가능한 파라미터가 되고, 이러한 파라미터를 최적화하여 학습이 진행됩니다. 또한 $\sigma$는 non-linearity를 가지는 activation function으로 ReLU나 tanh나 sigmoid 등 일반적인 인공 신경망에서 사용되는 함수들을 사용할 수 있습니다.

GCN(Graph Convolutional Network)

GCN은 ICLR 2017에서 발표된 논문으로, Thomas N. Kipf와 Max Welling이 제안하였습니다. 위의 간단한 아이디어와 크게 차이가 나지는 않지만, Neighborhood aggregation을 조금 다르게 함으로써 성능을 개선하였습니다.

GCN에서 $h_{v}^{k}$는 아래 식과 같이 구합니다.

$h_{v}^{k}$ = $ \sigma (W_{k} \sum_{{u \vert {u, v} \in E} \cup { v }} \frac{h_{u}^{k-1}}{\sqrt{\vert {w \vert {v, w} \in E} \vert \vert {w \vert {u, w} \in E} \vert}}) $

위의 간단한 아이디어에 나와있는 식과는 다음과 같은 차이점이 있습니다.

이웃들을 aggregate할 때는 $W_k$를 사용하였고, 자기 자신의 이전 embedding에는 $B_k$를 곱했는데, GCN에서는 자기 자신과 이웃에 대해서 동일한 파라미터인 $W_k$를 사용합니다.
위의 아이디어에서는 단순히 neighbor들의 embedding의 평균을 구한 것과 다르게, neighbor들끼리 aggregate할 때 normalization을 적용하여 차등적으로 반영한 것을 확인할 수 있습니다. 즉, 노드 $v$와 연결된 이웃으로 $u$와 $w$가 있고 $u$의 차수가 $w$보다 클 때, $w$의 embedding이 레이어를 거친 후의 embedding을 결정하는데 좀 더 크게 반영됩니다.

또한 행렬을 이용해서 아래와 같이 효율적으로 표현할 수 있습니다.

여기서 $H^{(k)}$는 k번째 레이어를 거친 후의 각 노드들의 embedding vector를 모두 포함하고 있는 행렬입니다. A는 인접행렬을 의미하고, 가장 아래의 식에서 D는 각 노드의 차수가 diagonal element인 대각행렬임을 알 수 있습니다. 위의 행렬로 이루어진 식을 사용하면 인공 신경망을 학습할 때 batch learning을 좀 더 효율적으로 진행할 수 있습니다.

GraphSAGE

GraphSAGE(SAmple and aggreGatE) 는 NIPS(NeurIPS) 2017에서 발표된 논문으로, William L. Hamilton, Rex Ying 그리고 Jure Leskovec이 제안하였습니다. 마찬가지로 위의 아이디어와는 크게 차이가 나지 않고, Neighborhood aggregation을 조금 다르게 하였습니다.

위의 사진에서의 'CONCAT'은 위에서 설명한 함수 이름이 아니라 원래의 이미 그대로 두 벡터를 합치는 기능을 합니다.

AGGREGATE 함수의 결과와 이전 레이어까지의 자기 자신의 embedding을 단순히 합쳐서 $W_k$와 곱한 값이 현재 레이어를 거친 후의 embedding이 됩니다.

GraphSAGE에서는 AGGREGATE 함수의 후보로 아래의 세 가지를 제안하였습니다.

Mean aggregator: 위의 ‘간단한 아이디어’와 동일합니다.
LSTM aggregator: RNN의 대표적인 것 중 하나인 LSTM을 사용하여 aggregate합니다. 그래프에서 이웃간의 순서를 정의할 수 있는 방법이 없기 때문에 random permutation을 사용하여 이웃들을 나열한 것이 LSTM의 입력으로 사용되고 출력 결과가 AGGREGATE 함수의 최종 결과가 됩니다. 당연하지만, 이웃들을 어떻게 나열하냐에 따라서 결과가 달라질 수 있습니다.
Pooling aggregator: 각각 이웃의 embedding들에 행렬 $W_{pool}$을 곱하고 벡터 $b$를 더한 후 max-pooling을 통해 얻은 결과를 사용합니다. 논문에 따르면 max-pooling과 mean-pooling 사이에 큰 차이를 느끼지는 못했다고 합니다. (실험은 max-pooling으로 진행하였기에, 여기서는 max-pooling으로 설명하였습니다.)

세 가지 다른 aggregator에 대해서 실험을 진행한 결과는 다음과 같습니다.

세 가지 후보 모두 기존의 방법론들보다 좋은 결과를 보여주었습니다. 그 중에서도 LSTM을 사용한 방법이 random permutation을 사용했음에도 굉장히 좋은 결과를 보여주는 것을 확인할 수 있습니다. 전체적으로 보았을 때, LSTM aggregator와 Pooling aggregator가 좋은 결과를 보여주었습니다. LSTM aggregator를 적용했을 때의 수행 속도가 Pooling aggregator를 사용했을 때보다 느려서 Pooling aggregator가 시간과 성능 모두 잡는 선택이라고 논문에서는 설명하고 있습니다.

마무리

이 포스트에서는 GNN이 어떤 것인지와 어떻게 작동하는지에 대해서 알아보았습니다. 그리고 GCN, GraphSAGE와 같이 GNN과 관련된 연구 결과에 대해서도 간단히 알아보았습니다.

GCN과 GraphSAGE가 발표된 이후에 Graph Attention Network나 LGCN 등이 발표되었으나, 여기서는 다루지 않았습니다. 좀 더 자세하게 공부해보고 싶다면 위에 설명된 논문들이나 새로 발표되는 GNN들에 대해서 공부해보면 좋을 것이라고 생각합니다.