GNN 심화

Andrew·2021년 2월 26일

그래프 신경망이란 무엇일까? (심화)

이번에는 그래프 신경망(Graph Neural Network, GNN)의 심화 내용이다

그래프 신경망의 기본적 연산에 한 때 엄청나게 핫했던 어텐션을 적용하는 내용을 배운다

또, 그래프 신경망의 결과물인 정점 임베딩으로부터 그래프 임베딩을 얻을 수 있는 그래프 풀링을 배운다

또, 그래프 신경망을 학습 시킬 때 일어날 수 있는 지나친 획일화(Over-Smoothing) 문제를 알아보자

어텐션을 적용하고 그래프 풀링을 통해 정점 임베딩으로부터 그래프 임베딩을 얻고, 이러한 학습을 할 때 일어날 수 있는 문제점까지 알게된다면 그래프신경망에 대한 지식이 엄청나게 늘어나게 될 것이다

Further Questions

GraphSAGE 모델에서는 하나의 정점을 나타내기 위하여 집계 함수를 활용합니다. 이때, 자기 자신만의 임베딩 뿐 아니라 이웃 정점의 임베딩까지 사용합니다. 이러한 방식으로 정점을 정의하게 된다면, 어떠한 장점이 있을까?
- ans : 학습 때 보지못한 노드가 등장하여도 적절한 라벨링이 가능해진다

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

기본 그래프 신경망의 한계

기본 그래프 신경망에서는 이웃들의 정보를 동일한 가중치로 평균 을 낸다
그래프 합성곱 신경망에서 역시 단순히 연결성을 고려한 가중치로 평균 을 낸다
- 단순한 형태의 정규화를 통해서 계산한 가중치로 평균을 낸다

그래프 어텐션 신경망

그래프 어텐션 신경망(Graph Attention Network, GAT) 에서는 가중치 자체도 학습 한다
- 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문이다
- 가중치를 학습하기 위해서 셀프-어텐션(Self-Attention) 이 사용된다
각 층에서 정점 $i$ 로부터 이웃 $j$ 로의 가중치 $\alpha_{ij}$ 는 세 단계를 통해 계산된다
- 해당 층의 정점 $i$ 의 임베딩 $h_i$ 에 신경망 $W$ 를 곱해 새로운 임베딩 을 얻는다
  - $\tilde{h_i} = h_iW$
- 정점 $i$ 와 정점 $j$ 의 새로운 임베딩을 연결한 후, 어텐션 계수 벡터 $a$ 를 내적한다
  - 어텐션 계수 $a$ 는 모든 정점이 공유하는 학습 변수이다
  - $e_{ij} = a^T[CONCAT(\tilde{h_i}, \tilde{h_j})]$
- 두번째의 결과에 소프트맥스(Softmax)를 적용한다
  - $\alpha_{ij} = softmax(e_{ij}) = \cfrac{exp(e_{ij})}{\sum_{k \in N(i)}exp(e_{ik})}$
여러 개의 어텐션을 동시에 학습 한 뒤, 결과를 연결하여 사용한다
- 멀티헤드 어텐션(Multi-head Attention) 이라고 부른다
  - $h_t^\prime = \underset{1 \le k \le K}{CONCAT} \sigma(\sum_{j \in N_i} \alpha^k_{ij}h_jW_k)$
  
  - $\alpha^k_{ij}$ : 가중치를 한개가 아닌 $k$ (위 그림에선 3개)개를 얻어서 집계한 결과를 연결(concat)해서 최종 임베딩을 얻는다
어텐션의 결과 정점 분류의 정확도(Accuracy)가 향상 되는 것을 확인할 수 있다

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

그래프 표현 학습

그래프 표현 학습 , 혹은 그래프 임베딩 이란 그래프 전체를 벡터의 형태로 표현 하는 것이다
- 개별 정점을 벡터의 형태로 표현하는 정점 표현 학습과 구분된다
- 그래프 임베딩 은 벡터의 형태로 표현된 그래프 자체를 의미하기도 한다
- 그래프 임베딩 은 그래프 분류 등에 활용된다
- 그래프 형태로 표현된 화합물의 분자 구조로부터 그래프 전체의 화합물의 특성을 예측하는 것이 한가지 예시이다

그래프 풀링

그래프 풀링(Graph Pooling) 이란 정점 임베딩들로부터 그래프 임베딩을 얻는 과정 이다
- 즉, 그래프 신경망을 사용하면 정점별 임베딩 벡터 표현을 얻는데 이것들을 합산하여 그래프 전체를 표현하는 벡터표현을 얻는 방법이다
- 평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우 그래프 분류 등의 후속 과제에서 더 높은 성능을 얻는 것으로 알려져 있다
- 아래 그림의 미분가능한 풀링(Differentiable Pooling, DiffPool) 방법은 군집 구조를 활용 임베딩을 계층적으로 집계한다
- 위 그림 과정 설명:
  - 그래프 신경망을 활용하여 정점별 임베딩 벡터를 얻은 후
  - 군집 구조를 이용해서 군집별로 임베딩을 합산을 한다
  - 합산된 결과에서 또다시 군집들을 찾아서 합산을 하고
  - 최종적으로 그래프 임베딩을 얻어서 classifier를 통과해서 그래프 분류 등의 활용한다
- 미분 가능한 풀링에는 그래프 신경망이 여러 곳에서 사용된다
  - 먼저 개별 정점의 임베딩을 얻는 과정에도 사용되고
  - 이 정점들을 군집구조로 묶어주는 과정에도 그래프 신경망이 사용된다
  - 그것들 군집내에서 합산 할때도 그래프 신경망이 사용된다

지나친 획일화 문제

지나친 획일화(Over-smoothing) 문제 란 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상 을 의미한다
- 지나친 획일화 문제는 작은 세상 효과 와 관련이 있다
  - 즉, 정점간의 거리가 너무 가까운데서 발생하는 문제이다
  - 아래처럼 층을 5개를 쌓게되면 5 만큼 거리가 떨어진 정점들의 정보를 집계한다
  - 많은 정점들의 사이가 가깝다 보니 5개 layer(거리 5) 정도면 수 많은 정점들로 부터 정보를 합산하기 때문에
  - 마치 지역적인 정보만 보는것이 아니라 그래프의 전반을 보게되는, 그래프의 전반을 집계하는, 효과가 있어서 정점들이 전부 비슷비슷한 임베딩을 얻게 된다
  - 결론적으로는 분류의 성능이 떨어진다
- 적은 수의 층으로도 다수의 정점에 의해 영향을 받게 된다
- 위 그래프를 살펴보면 정점별 임베딩의 위치를 보여준다
- 첫번째 layer를 통과한 이후에는 정점들의 임베딩이 널리 퍼져있는데
- layer를 통과하면 통과할수록 점점 가까워진다
- 5번째 layer를 통과한 이후에는 많은 정점들이 굉장히 유사한 임베딩을 얻는다

지나친 획일화 의 결과로 그래프 신경망의 층의 수를 늘렸을 때, 후속 과제에서의 정확도가 감소하는 현상 이 발견되었다
- 아래 그림에서 보듯이 그래프 신경망의 층이 2개 혹은 3개 일 때 정확도가 가장 높다
- 위 문제를 해결하기 위해서 잔차항을 넣는다
- 하지만 잔차항(Residual) 을 넣는 것, 즉 이전 층의 임베딩을 한 번 더 더해주는 것 만으로는 효과가 제한적이다
  - $h^{(l+1)}_u = h^{(l+1)}_u +$ $h^{(l)}_u$

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

획일화 문제에 대한 대응으로 JK 네트워크(Jumping Knowledge Network) 는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 최종 집계함수에 넣어줘서 최정 임베딩을 얻는데 사용한다
- APPNP 라는 그래프 신경망에서는 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화하였다
  - 즉, 함수에서 $W$ matrix에 해당하는 부분을 0번재 신견망에만 넣고 첫번째, 두번째, 세번째 신경망에서는 $W$ 를 없이해서 집계함수 자체를 단순화하는 방법을 사용했다

APPNP 의 경우, 층의 수 증가에 따른 정확도 감소 효과가 없는 것 을 확인했다
- 후속 과제로는 정점 분류가 사용되었다

그래프 데이터의 증강

데이터 증강(Data Augmentation) 은 다양한 기계학습 문제에서 효과적이다
- 그래프에도 누락되거나 부정확한 간선 이 있을 수 있고, 데이터 증강 을 통해 보완할 수 있다
- 임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법 이 제안되었다