[Day 25] GNN

[Day 25] GNN

 

 

1. 강의 복습 내용

1.1) GNN 기초

---

GNN

 

 

1. 정점 표현 학습

- 정점 표현 학습은 정점 임베딩(Node Embedding) 이라고도 한다.

- 그래프의 정점들을 벡터의 표현하는 것이 목적 (그래프에서의 정점간 유사도를 임베딩 공간에서도 보존)

- 앞에서 알아본 인접성/거리/경로/중첩/임의보행 기반 접근법은 모두 변환식 방법

 

- 변환식(Transdctive) 방법은 학습의 결과로 정점의 임베딩 자체를 얻음

- 귀납식(Inductive) 방법은 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는다.

- 대표적인 귀납식 임베딩 방법에는 그래프 신경망(Graph Neural Network)가 있다.

 

1.1) 변환식 방법의 한계

- 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다. (전체 그래프에서 다시 얻어야함)

- 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 한다. (메모리 리스크)

- 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없다. (표현력의 한계)

 

1.2) 귀납식 방법의 장점

- 변환식 방법의 한계를 모두 극복 가능함

- 학습이 진행된 이후에 추가된 정점에 대해서도 임베딩을 얻을 수 있다. (인코더를 얻기 때문)

- 모든 정점에 대한 임베딩을 미리 계산하여 저장해둘 필요가 없다. (인코더를 통해 필요할 때 임베딩을 얻음)

- 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 있다.

---

2. 그래프 신경망 기본

2.1) 그래프 신경망 구조

그래프 신경망의 구조

 

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

(예를 들어, 각 정점의 속성을 담은 벡터들로 구성한 인접 행렬을 구성할 수 있음)

 

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

 

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

(각 층에서는 이웃들의 이전 층 임베딩을 집계하여 새로운 임베딩을 얻는다.)

 

- 따라서 입력은 각 노드의 정보를 담은 벡터가 담겨져 있으므로, 0층의 임베딩은 정점의 속성 벡터를 사용한다.

 

- 서로 다른 대상 정점간에도 같은 층의 집계 함수는 공유한다.

 

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

각 층의 집계 함수의 수식 표현

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

마지막 층에서의 출력 임베딩 (결국 동일한 수식이 층을 거치면서 재귀적으로 연산이 일어나고 마지막 층에서의 결과가 아웃풋)

2.2) 그래프 신경망의 학습

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

각 층에서의 임베딩 함수에서 학습되는 Paramters

 

- 그래프 신경망을 학습 시키기 위해서는 먼저, 손실함수를 결정해야 한다.

- 손실함수는 정점간 거리를 어떻게 정의하느냐 에 따라 여러가지로 결정할 수 있다.

- 또한, Downstream Task의 손실함수를 이용한 종단종(End-to-End) 학습도 가능하다.

(예를 들어, 각 정점을 Classification하는 Task에서는 손실함수를 Cross Entropy로 정의할 수 있음)

그래프 신경망의 End-to-End Learning의 모델 구조

---

3. 그래프 신경망 변형

- 앞에서 살펴본 그래프 신경망의 집계 함수를 다양한 형태의 집계 함수로 변형하여 사용할 수 있다.

- 그 중에서 대표적인 것이 바로 그래프 합성공 신경망(Graph Convolutional Network, GCN)의 집계 함수

3.1) GCN

GCN의 집계 함수

GNN과 GCN의 집계 함수 비교

- GNN은 집계가 되고 있는 정점의 이전 레이어에서의 임베딩을 별도의 신경망을 이용하여 합계를 해주었지만, GCN은 동일 신경망으로 사용하였다.

- 또한 정규화 방법에서도 GNN은 v의 연결성만 사용하였다면, GCN은 u와 v의 연결성의 기하평균을 사용함

- 이러한 작은 차이로도 큰 성능의 향상으로 이어지기도 한다.

 

3.2) GraphSAGE

GraphSAGE의 집계 함수

 - AGG 함수를 다양하게 사용할 수 있다.

AGG의 다양한 옵션을 사용하여 GraphSAGE의 집계 함수도 다양하게 사용할 수 있다.

---

4. 그래프 신경망과 CNN(합성곱 신경망)의 비교

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

- 하지만, CNN은 이웃의 수가 균일하지만(대부분 이미지의 픽셀), 그래프 신경망에서는 균일하지 않다.

- 따라서 그래프의 인접행렬을 가지고 CNN을 적용해봤자 효과적이지 않다.

 

*) 다시 정리하자면, CNN은 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높기 때문에 적용되는 것이고, 그래프의 인접 행렬에서는 인접 원소는 제한된 정보를 가진다. (인접 행렬의 행과 열의 순서는 임의로 결정되므로)

 

---

1.2) GNN 심화

---

GNN 심화

 

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

1.1) 기본 그래프 신경망의 한계

- 기본 그래프 신경망에서는 이웃들의 정보를 동일한 가중치로 평균을 낸다.

- 그래프 합성공 신경망에서도 역시 단순히 연결성을 고려한 가중치로 평균을 낸다.

GNN, GCN 모두 집계 함수에서 이웃들의 정보(혹은 연결성)로 평균을 낸다.

 - 즉, 그래프에서 이웃 별로 미치는 영향을 각각 다를 수 있지만 기존의 집계 함수에서는 단순 평균을 구하기 때문에 고려할 수 없다는 한계가 있다.

 

1.2) 그래프 어텐션 신경망

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

- 기본 그래프 신경망의 한계(이웃 별로 미치는 영향을 고려)를 보완하기 위해서 Self-Attention이 사용된다.

각 정점들의 이웃의 중요도를 셀프 어텐션으로 학습하여 가중치로 매긴다.

그래프 신경망에서 Self-Attetion 학습하는 과정

- 위의 W벡터와 a벡터는 Self-Attention을 학습하면서 학습되어지는 Parameter이다.

- 또한 이웃별 가중치를 두 개 이상으로 표현할 수 있으며, 이 때에는 여러 개의 어텐션을 동시에 학습한 뒤에 결과를 Concat하여 사용한다. 이를 멀티헤드 어텐션(Multi-head Attention) 이라고 부른다.

Multi-head Attention 그래프 신경망의 예시

---

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

2.1) 그래프 표현 학습

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

- 개별 정점을 벡터의 형태로 표현하는 정점 표현 학습과 구분된다.

- 그래프 임베딩은 벡터의 형태로 표현된 그래프 자체이다.

 

- 그래프 임베딩은 그래프 분류 등에 활용될 수 있다. (그래프들을 각각 벡터로 표현할 수 있으므로)

 

2.2) 그래프 풀링

- 그래프 풀링(Graph Pooling)이란, 정점 임베딩(정점 표현 학습)들로부터 그래프 임베딩을 얻는 과정

- 평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우, 그래프 분류 등 다운스트림 태스크에서 더 높은 성능을 얻을 수 있다.

그래프 풀링의 예시 (Differentiable Pooling, DiffPool)

- 위의 그림처럼, 그래프 신경망을 사용하여 정점 별 임베딩을 얻고, 군집 구조를 활용하여 군집 별 임베딩을 합산하고 최종적으로 하나의 군집으로 나타내면 최종적으로 그래프의 임베딩을 얻을 수 있다.

---

3. 지나친 획일화 문제

3.1) 지나친 획일화 문제와 작은 세상 효과

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

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

- 왜냐하면 레이어를 5개를 쌓는 다는 것은, 5만큼의 거리에 있는 정점들 까지도 고려하는 것인데, 작은 세상 효과와 같이 아주 큰 그래프일지라도 5~6번의 거리만큼만 가면 그래프의 끝과 끝을 탐색할 수 있다는 문제가 있다.

- 즉, 층을 많이 쌓으면 쌓을 수록 결국 정점 간 임베딩은 모두 유사해지는 것이다.

지나친 획일화 문제의 예시

지나친 획일화 문제로 인한 모델 성능 감소

- 이러한 문제를 해결하기 위해서 위의 예시처럼 전차항(Residual)을 넣는 것, 즉 이전 층의 임베딩을 한번 더 더해주는 것도 시도하였지만, 효과는 제한적이였다.

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

- 이전 층의 임베딩을 한번 더 더해주는 시도도 있었지만, 효과는 미비하였다.

- 하지만 JK 네트워크(Jumping Knowledge Network)는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용함으로써 이러한 문제를 대응하였다.

- 또한, APPNP은 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화 하였다.

 

---

4. 그래프 데이터 증강

- 데이터 증강(Data Augmentation)은 다양한 기계학습 문제에서 효과적이다. (데이터가 많아지기 때문에)

- 예를 들어, 이미지 관련 데이터에서는 이미지를 반전시키거나 회전시키고 자르고 하는 방식으로 데이터를 증강시킬 수 있었다.

- 그래프에서도 역시, 데이터 증강이 가능하며 누락되거나 부정확한 간선을 보완할 수 있다.

 

- 임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법이 제안됨

신경망에 입력하기 전, 정점간 유사도를 계산해보고 필터링하여 데이터를 증강한 후 증강한 그래프를 신경망에 입력한다.

- 이러한 그래프 데이터 증강의 결과, 정점 분류의 정확도가 개선되는 것 또한 입증되었다.

Heat과 PPR은 그래프 데이터 증강 기법을 사용한 결과

---

2. 피어 세션

---

1. 강의에 대한 토의

- GNN에서 정점 표현 학습은 비지도 학습, 정점을 Classification하는 것은 지도 학습인데, 어떻게 Cross-Entropy 손실함수로 End-to-End 학습이 가능할까? -> NLP에선, 비슷한 예로 단어간 유사도를 구하는 비지도 학습을 사전 학습을 통해 가져와 사용한 예시가 있음. -> NLP에서도 이 같은 경우가 가능할까? (BERT의 모델구조만 가져와 Classification task를 수행해보자)

- 완전그래프에 CNN을 적용하면 어떨까? (연결된 모든 정점을 고려할 순 없을 것 같다) -> 이 역시 효율이 떨어짐

- AGG 함수에서 LSTM

 

- 그래프 신경망과 NLP

---

3. Conclusion

---

1. 그래프 신경망과 NLP

그래프에서도 결국 각 정점들을 임베딩하고 임베딩된 정점들을 통해 신경망에서 유사도를 구하고 그것을 가지고 다운스트림 태스크를 수행할 수 있다.

NLP에서도 각 토큰화된 단어들을 임베딩하고, 임베딩된 단어들을 통해 단어간 유사도를 구하고 그것을 가지고 다운스트림 태스크를 수행할 수 있다.

 

즉 그래프와 NLP 과정은 유사한 것으로 보인다.

 

그래프에서는 사전에 임베딩하여 유사도를 구하는 방식 -> 변환식 정점 표현, 즉 출력이 임베딩으로 나오고

재귀식 정점 표현에서는, 임베딩을 구하는 함수를 구하는 방식(즉 모델안에서 유사도를 직접 구할 수 있음) -> End-to-End 러닝이 가능한 이유 인것인가?

 

그렇다면 NLP도 마찬가지로 그래프에서 변환식 정점 표현으로 해당되는 것이 Word2Vec과 GloVe 같은 것인가? 재귀식 정점 표현은 Transfomer를 사용한 모델(Bert, GPT 등) 들을 말하는 것인가?

 

- 지도 학습

- 비지도 학습

- Self-Superviself-supervised learning

---