그래프 신경망

정점 표현 학습

정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것입니다.

정점 표현 학습은 간단히 정점 임베딩(Node Embedding)이라고도 부릅니다.
정점 표현 학습의 입력은 그래프입니다.
주어진 그래프의 각 정점 $u$ 에 대한 임베딩, 즉 벡터 표현 $z_u$ 가 정점 임베딩의 출력입니다.

그래프에서의 정점간 유사도를 임베딩 공간에서도 '보존'하는 것을 목표로 합니다.

그래프에서 두 정점의 유사도는 어떻게 정의할까요?

그래프에서 정점의 유사도를 정의하는 방법에 따라 인접성/거리/경로/중첩/임의보행 기반 접근법으로 나뉩니다.

변환식 정점 표현 학습과 귀납식 정점 표현 학습

지금까지 소개한 정점 임베딩 방법들을 변환식(Transductive) 방법_입니다.

변환식(Transdctive) 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있습니다.
정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식 (Inductive) 방법과 대조됩니다.

출력으로 임베딩 자체를 얻는 변환식 임베딩 방법은 여러 한계를 갖습니다.

1) 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없습니다.
2) 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 합니다.
3) 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없습니다. 성별, 나이, 지역 정보를 가질 때 이를 임베딩 벡터에 반영할 수 없습니다.

출력으로 인코더를 얻는 귀납식 임베딩 방법은 여러 장점을 갖습니다.

1) 학습이 진행된 이후에 추가된 정점에 대해서도 임베딩을 얻을 수 있습니다.
2) 모든 정점에 대한 임베딩을 미리 계산하여 저장해둘 필요가 없습니다.
3) 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 있습니다.

---

그래프 신경망 기본

그래프 신경망 구조

그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받습니다.

그래프의 인접 행렬을 $A$ 라고 합시다.
인접 행렬 $A$ 은 $|V| \times |V|$ 의 이진 행렬입니다.

각 정점 $u$ 의 속성(Attribute) 벡터를 $X_u$ 라고 합시다.
정점 속성 벡터 $X_u$ 는 $m$ 차원 벡터이고, $m$ 은 속성의 수를 의미합니다.

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

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

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

예시에서 대상 정점의 임베딩을 얻기 위해 이웃들 그리고 이웃의 이웃들의 정보를 집계합니다.

각 집계 단계를 층(Layer)이라고 부르고, 각 층마다 임베딩을 얻습니다.

각 층에서는 이웃들의 이전 층 임베딩을 집계하여 새로운 임베딩을 얻습니다. 0번 층, 즉 입력 층의 임베딩으로는 정점의 속성 벡터를 사용합니다.

대상 정점 마다 집계되는 정보가 상이합니다.

대상 정점 별 집계되는 구조를 계산 그래프(Computation Graph)라고 부릅니다.

서로 다른 대상 정점간에도 층 별 집계 함수는 공유합니다.

각 정점별 이웃이 다르기 때문에 입력의 크기가 다르다.
서로 다른 구조의 계산 그래프를 처리하기 위해서는 어떤 형태의 집계 함수가 필요할까요?

집계 함수는 (1) 이웃들 정보의 평균을 계산하고 (2) 신경망에 적용하는 단계를 거칩니다.

마지막 층에서의 정점 별 임베딩이 해당 정점의 출력 임베딩입니다.

$h_v^{k-1}$은 k-1 층에서의 자기 자신의 임베딩 정보

그래프 신경망의 학습

그래프 신경망의 학습 변수(Trainable Parameter)는 층 별 신경망의 가중치입니다.

먼저 손실함수를 결정합니다. 정점간 거리를 '보존'하는 것을 목표로 할 수 있습니다.

변환식 정점 임베딩에서처럼 그래프에서의 정점간 거리를 '보존'하는 것을 목표로 할 수 있습니다.

만약, 인접성을 기반으로 유사도를 정의한다면, 손실 함수는 다음과 같습니다.

후속 과제(Downstream Task)의 손실함수를 이용한 종단종(End-to-End) 학습도 가능합니다.

정점 분류가 최종 목표인 경우를 생각해봅시다.

예를 들어,
(1) 그래프 신경망을 이용하여 정점의 임베딩을 얻고
(2) 이를 분류기(Classifier)의 입력으로 사용하여
(3) 각 정점의 유형을 분류하려고 합니다.

이 경우 분류기의 손실함수, 예를 들어 교차 엔트로피(Cross Entropy)를 전체 프로세스의 손실함수로 사용하여 종단종(End-to-End) 학습을 할 수 있습니다.

그래프 신경망과 변환적 정점 임베딩을 이용한 정점 분류

그래프 신경망의 종단종(End-to-End) 학습을 통한 분류는 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높습니다.

아래 표는 다양한 데이터에서의 정점 분류의 정확도(Accuracy)를 보여줍니다.

학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성합니다.

선택한 대상 정점들에 대한 계산 그래프를 구성합니다.

마지막으로 오차역전파(Backpropagation)를 통해 손실함수를 최소화합니다.

구체적으로, 오차역전파를 통해 신경망의 학습 변수들을 학습합니다.

그래프 신경망의 활용

학습데이터를 구성할 때는 모든 정점들을 사용할 필요는 없습니다.

학습된 신경망을 적용하여 학습에 사용되지 않은 정점의 임베딩을 얻을 수 있습니다.

마찬가지로, 학습 이후에 추가된 정점의 임베딩도 얻을 수 있습니다.

온라인 소셜네트워크 등 많은 실제 그래프들은 시간에 따라서 변화합니다.

학습된 그래프 신경망을, 새로운 그래프에 적용할 수도 있습니다.

예를 들어, A종의 단백질 상호 작용 그래프에서 학습한 그래프 신경망을
B종의 단백질 상호작용 그래프에 적용할 수 있습니다.

---

그래프 신경망 변형

그래프 합성곱 신경망

소개한 것 이외에도 다양한 형태의 집계 함수를 사용할 수 있습니다.

그래프 합성곱 신경망(Graph Convolutional Network, GCN)의 집계 함수입니다.

기존의 집계 함수와 비교해보겠습니다. 작은 차이지만 큰 성능의 향상으로 이어지기도 합니다.

$k-1$ 층의 $v$ 를 학습시키는 $B_k$ 가 $W_k$ 와 합쳐졌고, 정규화 방법으로 기하평균을 사용하였습니다.

GraphSAGE

GraphSAGE의 집계 함수입니다.

이웃들의 임베딩을 AGG 함수를 이용해 합친 후,
자신의 임베딩과 연결(Concatenation)하는 점이 독특합니다.

AGG 함수로는 평균, 풀링, LSTM 등이 사용될 수 있습니다.

위 LSTM의 수식에서 $\pi$ 는 이웃들의 임베딩을 가져와서 순서를 섞는 것을 뜻합니다. 순서를 섞은 뒤, LSTM의 입력으로 줍니다.

---

합성곱 신경망과의 비교

합성곱 신경망과 그래프 신경망의 유사성

합성곱 신경망과 그래프 신경망은 모두 이웃의 정보를 집계하는 과정을 반복합니다.

구체적으로, 합성곱 신경망은 이웃 픽셀의 정보를 집계하는 과정을 반복합니다.

합성곱 신경망과 그래프 신경망의 차이

합성곱 신경망에서는 이웃의 수가 균일하지만, 그래프 신경망에서는 아닙니다.

그래프 신경망에서는 정점 별로 집계하는 이웃의 수가 다릅니다.

그래프의 인접 행렬에 합성곱 신경망을 적용하면 효과적일까요?

그래프에는 합성곱 신경망이 아닌 그래프 신경망을 적용하여야 합니다.
많은 분들이 흔히 범하는 실수입니다.

합성곱 신경망이 주로 쓰이는 이미지에서는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높습니다.

하지만 그래프의 인접 행렬에서의 인접 원소는 제한된 정보를 가집니다. 특히나 인접 행렬의 행과 열의 순서는 임의로 결정되는 경우가 많습니다.

그래프 신경망(심화)

그래프 신경망

귀납식 정점 표현 학습

정점을 임베딩하는 함수, 즉 인코더를 학습하는 귀납식 정점 표현 학습은 여러 장점을 갖습니다.

1) 학습이 진행된 이후에 추가된 정점에 대해서도 임베딩을 얻을 수 있습니다.
2) 모든 정점에 대한 임베딩을 미리 계산하여 저장해둘 필요가 없습니다.
3) 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 있습니다.

그래프 신경망(Graph Neural Network)은 대표적인 귀납식 임베딩 방법입니다.

그래프 신경망의 구조

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

집계 함수의 형태에 따라, 그래프 신경망, 그래프 합성곱 신경망, graphSAGE 등이 구분됩니다.

그래프 신경망은 비지도 학습, 지도 학습이 모두 가능합니다.

비지도 학습에서는 정점간 거리를 '보존'하는 것을 목표로 합니다.
지도 학습에서는 후속 과제의 손실함수를 이용해 종단종 학습을 합니다.

그래프 신경망의 활용

학습된 신경망을 적용하여, 학습에 사용되지 않은 정점, 학습 이후에 추가된 정점, 심지어 새로운 그래프의 정점의 임베딩을 얻을 수 있습니다.

---

그래프 신경망에서의 어텐션

기본 그래프 신경망의 한계

기본 그래프 신경망에서는 이웃들의 정보를 동일한 가중치로 평균을 냅니다.
그래프 합성곱 신경망에서 역시 단순히 연결성을 고려한 가중치로 평균을 냅니다.

그래프 어텐션 신경망

그래프 어텐션 신경망(Graph Attention Network, GAT)에서는 가중치 자체도 학습합니다.

실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문입니다.
가중치를 학습하기 위해서 셀프-어텐션(Self-Attention)이 사용됩니다.

각 층에서 정점 $i$ 로부터 이웃 $j$ 로의 가중치 $\alpha_{ij}$ 는 세 단계를 통해 계산합니다.

1) 해당 층의 정점 $i$ 의 임베딩 $h_i$ 에 신경망 $W$ 를 곱해 새로운 임베딩을 얻습니다.

2) 정점 $i$ 와 정점 $j$ 의 새로운 임베딩을 연결한 후, 어텐션 계수 $a$ 를 내적합니다. 어텐션 계수 $a$ 는 모든 정점이 공유하는 학습 변수입니다.

3) 2)의 결과에 소프트맥스(Softmax)를 적용합니다.

여러 개의 어텐션을 동시에 학습한 뒤, 결과를 연결하여 사용합니다.

멀티헤드 어텐션(Multi-head Attention)이라고 부릅니다.

어텐션의 결과 정점 분류의 정확도(Accuracy)가 향상되는 것을 확인할 수 있었습니다.

---

그래프 표현 학습과 그래프 풀링

그래프 표현 학습

그래프 표현 학습, 혹은 그래프 임베딩이란 그래프 전체를 벡터의 형태로 표현하는 것입니다.

개별 정점을 벡터의 형태로 표현하는 정점 표현 학습과 구분됩니다.
그래프 임베딩은 벡터의 형태로 표현된 그래프 자체를 의미하기도 합니다.

그래프 임베딩은 그래프 분류 등에 활용됩니다.
그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측하는 것이 한가지 예시입니다.

그래프 풀링

그래프 풀링(Graph Pooling)이란 정점 임베딩들로부터 그래프 임베딩을 얻는 과정입니다.

평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우 그래프 분류 등의 후속 과제에서 더 높은 성능을 얻는 것으로 알려져 있습니다.

아래 그림의 미분가능한 풀링(Differentiable Pooling, DiffPool)은 군집 구조를 활용 임베딩을 계층적으로 집계합니다.

---

지나친 획일화 문제

지나친 획일화 문제

지나친 획일화(Over-smoothing) 문제란 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상을 의미합니다.

지나친 획일화 문제는 작은 세상 효과와 관련이 있습니다.
적은 수의 층으로도 다수의 정점에 의해 영향을 받게 됩니다.

5 layer 로 그래프 신경망을 구성하면 거리 5만큼 떨어진 정점들의 정보를 집계를 합니다. 거리 5 정도면 수많은 정점들로부터 정보를 합산합니다. 따라서 지역적인 정보를 보는 것이 아닌 그래프 전반의 정보를 집계하는 효과가 되어 정점들이 비슷비슷한 임베딩을 얻게됩니다.

지나친 획일화의 결과로 그래프 신경망의 층의 수를 늘렸을 때, 후속 과제에서의 정확도가 감소하는 현상이 발견되었습니다.

아래 그림에서 보듯이 그래프 신경망의 층이 2개 혹은 3개 일 때 정확도가 가장 높습니다.

잔차항(Residual)을 넣는 것, 즉 이전 층의 임베딩을 한 번 더 더해주는 것 만으로는 효과가 제한적입니다.

$h_u^{(l+1)} = h_u^{(l+1)}+$$\;h_u^{(l)}$

지나친 획일화 문제에 대한 대응

획일화 문제에 대한 대응으로 JK 네트워크(Jumping Knowledge Network)는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용합니다.

APPNP는 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화하였습니다.

APPNP의 경우, 층의 수 증가에 따른 정확도 감소 효과가 없는 것을 확인했습니다.

후속 과제로는 정점 분류가 사용되었습니다.

---

그래프 데이터의 증강

그래프 데이터 증강

데이터 증강(Data Augmentation)은 다양한 기계학습 문제에서 효과적입니다.

그래프에도 누락되거나 부정확한 간선이 있을 수 있고, 데이터 증강을 통해 보완할 수 있습니다.
임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법이 제안되었습니다.

그래프 데이터 증강의 효과

그래프 데이터 증강의 결과 정점 분류의 정확도가 개선되는 것을 확인했습니다.

아래 그림의 HEAT과 PPR은 제안된 그래프 데이터 증강 기법을 의미합니다.