Contents

  1. Graph Neural Network의 기본
    1. Structure of graph neural network
    2. Training of GNN
    3. Usage of graph neural network
  2. Advanced Graph Neural Network
    1. Graph Comvolutional Network
    2. GraphSAGE

이번 포스팅에서는 정점 표현 학습(Node Representation Learning)의 방법 중 한 가지인 그래프 신경망(Graph Neural Network, GNN)에 대해 다룰 예정이다. 최근 딥러닝에서 촉망 받고 있는 그래프 신경망, 과연 무엇을 학습시키는 것이고 어떤 방식으로 학습이 이루어질까? 그리고, 이전에 나온 합성곱 신경망(Convolutional Neural Network)과 어떤 점이 다른 것일까요?


Graph Neural Network의 기본

이전 포스팅에서 변환식 임베딩 방식과 귀납식 임베딩 방식을 간략히 언급했었다. review를 위해 간단히 다시 언급하자면, Transductive(변환식) 임베딩 방식은 학습의 결과로 Graph의 각 vertex에 대한 임베딩 자체를 얻는 방법이다. 반면에 Inductive(귀납식) 임베딩 방식은 graph의 vertex들을 임베딩으로 변환하는 함수 그 자체를 얻는 방식이다.

우리가 이번에 살펴볼 Graph Neural Network는 대표적인 Inductive 임베딩 방식의 한 종류라고 할 수 있다.


Structure of graph neural network

그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받는다. 특히 여기서 그래프를 입력으로 받을 때 인접행렬(Adjacency Matrix)를 입력으로 받는다. 또 다른 input인 속성정보는 각 정점 $u$의 속성(attribute) 벡터 $X_u$로 받는다.

여기서 $X_u$는 $m$차원 벡터이며, $m$은 속성의 수를 의미한다.

정점의 속성 예시는 다음과 같다.

  • 온라인 소셜 네트워크에서 사용자의 지역, 성별, 연령, 프로필 사진 등
  • 논문 인용 그래프에서 논문에 사용된 키워드에 대한 원-핫 벡터
  • PageRank 등의 정점 중심성, 군집 계수(Clustering Coefficient) 등

그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.

  • 아래 그림에서 대상 정점의 임베딩을 얻기 위해 Neighborhoods 그리고 neighborhoods of neighborhoods의 정보를 집계한다.

    image

  • 대상 정점 A의 임베딩을 얻기 위해서 A의 이웃, 그리고 그 이웃의 이웃 노드들을 집계함으로써 A의 임베딩을 얻을 수 있다.

  • 여기서 각 집계의 단계를 Layer로 정의하고 각 층마다 임베딩을 얻는다.

    image

  • 이때, 대상 정점을 얻기 위한 첫 번째 과정으로, 위 그림과 같이 0번 층에서 2번층(대상 정점) 방향으로 임베딩을 진행(집계)한다.
  • 또한, 0번 층, 즉 입력 층의 임베딩으로는 정점의 속성 벡터를 사용한다.
  • 그런데, 여기서 대상 정점이 무엇이냐에 따라서 대상 정점 별 집계되는 정보가 상이하다.

  • 주어진 graph에 대한 모든 정점들에 대하여 대상 정점 별 집계되는 구조를 계산 그래프(Computation graph)라고 부른다.

    image

  • 이러한 계산 그래프에서의 서로 다른 대상 정점간에도 Layer에 따른 집계 함수는 공유한다.

    image

  • 서로 다른 층에서는 서로 다른 집계함수를 사용하는 것이 일반적이다.
  • 하지만, 위 그림과 같이 같은 집계함수(예를들어 layer1 에서 layer2로 가는 집계함수)을 살펴보면, 집계함수는 같지만 input node가 각각 3개, 2개임을 볼 수 있다. 즉 가변적으로 입력의 크기를 처리해야한다.
  • 이처럼 서로 다른 구조의 Computation graph를 처리하기 위해서 어떤 형태의 집계함수가 필요할까?

가변적으로 변하는 입력 데이터로부터 동일한 input 사이즈를 가지는 집계함수를 구성하기 이를 위해서는 크게 2가지 과정을 거친다.

  • Neighbor node의 평균을 계산
  • 신경망에 적용

집계함수가 구성되는 위의 두 과정을 수식으로 나타내면 다음과 같다.

\[\begin{align} \mathbf{h}_v^0&=\mathbf{x}_v\\ \mathbf{h}_v^k&=\sigma\left(\mathbf{W}_k\sum_{u\in N(v)}\frac{\mathbf{h}_u^{k-1}}{\vert N(v)\vert}+\mathbf{B}_k\mathbf{h}_v^{k-1} \right), \forall k>0 \end{align}\]
  • $\mathbf{h}_v^0$ : 0번 층에서 정점 $v$의 임베딩으로 정점 $v$의 속성 벡터로 초기화
  • $\mathbf{h}_v^k$ : 현재 층, 즉 k번 층에서 정점 $v$의 임베딩 벡터
  • $\sigma$ : 비선형 활성화함수
  • $\sum_{u\in N(v)}\frac{\mathbf{h}_u^{k-1}}{\vert N(v)\vert}$ : 이전 층에서 이웃들의 임베딩에 대한 평균을 계산
  • $\mathbf{h}_v^{k-1}$ : 이전 층에서 정점 $v$의 임베딩

이 과정을 진행 후 0번째 층에서의 임베딩(입력 속성 정보)부터 마지막 층까지를 진행한 뒤 출력 임베딩으로 해당 정점 별 임베딩을 계산한다.

이때, 그래프 신경망의 학습 변수(Trainable Parameter)는 층 별 신경망의 가중치인 $\mathbf{W}_k$와 $\mathbf{B}_k$가 된다. 나머지 hidden state들도 학습 과정에서 바뀌긴 하지만, 직접적으로 학습이 되는 파라미터는 위와 같다고 할 수 있다.


Training of GNN

학습을 정의하기 위해서는 Loss function을 결정해야한다. 여기서 목표는 정점간의 거리를 보존하는 것이다.

이전 포스팅에서 다양한 방식의 transductive node embedding(변환식 정점 임베딩)의 loss function과 비슷하게, 그래프에서의 정점간 거리를 “보존”하는 것을 loss function의 목표로 한다. 만약 인접성을 기반으로 유사도를 정의한다면 손실함수는 다음과 같이 정의할 수 있다.

\[\mathcal{L} = \sum_{(u,v)\in V\times V}\vert\vert \mathbf{z}_u^\top\mathbf{z}_v - \mathbf{A}_{u,v} \vert\vert^2\]

또한, 후속 과제(Downstream Task)의 손실함수를 이용한 end-to-end 학습도 가능하다. 예를들어 node classification이 최종 목표인 경우를 생각해보자.

  • 그래프 신경망을 이용하여 정점의 임베딩을 얻고
  • 이를 분류기의 입력으로 사용한 뒤
  • 각 정점의 유형을 분류한다.

와 같은 과정으로 node classification을 진행하려 한다. 여기서의 목표는 각 정점의 임베딩 공간에서의 유사도를 그래프에서의 유사도로 근사시키는 것이 목적이 아니라 해당 임베딩 벡터를 사용하고, 분류기를 통과한 뒤 분류 정확도를 높이는 것이다. 좋은 그래프 임베딩 공간을 찾는 것도 중요하지만, 이 경우 분류의 정확성을 높이는 것이 더 중요하기 때문이다.

이 경우 분류기의 성능을 더 좋게하는 loss function을 사용해야만 하고, 위의 경우에(분류 task)는 아래 식과 같이 Cross Entropy를 사용한다. node embedding을 진행하는 식과는 상이하지만, 궁극적으로는 정점의 실제 class와 해당 정점의 임베딩 벡터, 그리고 분류기의 학습 변수를 사용하여 loss를 정의하는 것을 확인할 수 있다.

image

image

단순히 Classifier에서만 역전파를 계산하는 것이 아니라 node embedding 가장 첫 layer까지 진행하며 학습하게 된다.

변환적 정점 임베딩을 학습한 이후에, 분류기를 별도로 학습하는 방식과 그래프 신경망의 종단종(end-to-end) 학습을 통한 분류를 비교하였을 때에는 일반적으로 종단종 분류가 훨씬 높은 정확도를 보여주었다.
아래 GCN은 graph convolutional network로써 대표적인 그래프 신경망을 이용한 종단종 학습 방식 중 하나이다.

해당 내용(GCN)에 대한 자세한 설명은 따로 포스팅하였으니 하는 중이니.. 참고하는 것을 추천한다.

image

손실함수를 정의한 이후에는 학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성한다. 모든 정점을 사용할 필요가 없는 이유는 Computation graph에서 Layer가 동일할 때 집계함수가 같고, 이를 모두 공유하기 때문에 일부 대상 정점을 선택하여 계산 그래프를 구성한다.

image

마지막으로 역전파를 통해 Loss function을 최소화한다. 구체적으로, 역전파를 통해 신경망의 학습 변수들을 학습하게 된다.

image


Usage of graph neural network

이렇게 학습된 신경망을 적용하여, 학습 이후에 추가된 정점의 임베딩도 얻을 수 있다. 온라인 소셜 네트워크 등 많은 실제 그래프는 시간에 따라서 변화한다.

image

새로운 정점이 추가되었을 때, 그래프 신경망을 적용하여 새 정점에 대한 임베딩을 계산할 수 있다.

심지어 학습된 그래프 신경망을, 새로운 그래프에도 적용할 수 있다. 예를 들어, A종 단백질 상호 작용 그래프에서 학습한 그래프 신경망을 B종 단백질 상호작용 그래프에 적용할 수도 있다.

image


Advanced Graph Neural Network

지금까지 가장 간단한 형태의 GNN을 살펴보았다면, 지금부터 소개할 신경망은 이를 변형하여 가장 많이 사용하는 형태의 두 가지 신경망에 대한 내용이다.

앞서 살펴보았듯이 그래프의 집계함수를 어떤 것으로 선택하느냐에 따라 다양한 형태로 디벨롭 시킬 수 있다.

image


Graph Comvolutional Network

아래 식은 GCN(Graph Convolutional Network)의 집계함수이다.

\[\begin{align} \mathbf{h}_v^0&=\mathbf{x}_v\\ \mathbf{h}_v^k&=\sigma\left(\mathbf{W}_k\sum_{u\in N(v)\cup v}\frac{\mathbf{h}_u^{k-1}}{\sqrt{\vert N(u)\vert\vert N(v)\vert}}\right), \forall k\in \left\{1,\dots, K\right\}\\ \mathbb{z}_v&=\mathbb{h}_v^K \end{align}\]

GCN과 기본 GNN의 집계함수를 비교하며 살펴보자

image

GNN에서는 이전 layer로부터 들어온 hidden state를 $\mathbf{B}_k$라는 신경망을 이용해 학습했다면, GCN에서는 이를 하나로 통합하여 $\mathbf{W}_k$로 하나로 합쳐 학습하는 것을 확인할 수 있다. 이는 Summation 기호 아래 $u\in N(v)\cup u$를 통해 알 수 있다.

또 하나는, 정규화 부분이다. 기존 GNN에서는 $v$와의 연결성만을 확인했다면, GCN에서는 $u$와 $v$의 연결성의 기하 평균을 사용했음을 알 수 있다.


GraphSAGE

graphSAGE는 Inductive Representation Learning on Large Graphs에서 처음 소개되었다.

GraphSAGE의 집계함수를 살펴보면, 이웃들의 임베딩을 AGG함수를 이용해 합친 후, 자신의 임베딩과 연결(Concatenation)하는 점이 독특하다. 그 식은 아래와 같다.

\[\mathbf{h}_v^k=\sigma(\left[\mathbf{W}_k\cdot\text{AGG}(\left\{ \mathbf{h}_u^{k-1},\forall u\in N(v) \right\}),{\mathbf{B}_k\mathbf{h}_v^{k-1}}\right])\]

이때, Aggregation 함수에는 다음과 같이 다양한 함수를 사용할 수 있다.

image

  • LSTM의 $\pi$는 정점의 neighbor를 가져온 뒤 순서를 섞어 LSTM에 넣어준다고 생각하면 된다.


Further Reading