Contents

  1. Graph neural network with attention
    1. Graph attention networks(GATs)
  2. Graph representation learning
  3. Graph Pooling
  4. Over-smoothing Problem
  5. Graph data augmentation

이번 포스팅은 그래프 신경망(Graph Neural Network, GNN)의 심화 내용을 다룰 예정이다. 특히, 그래프 신경망의 기본적 연산에 어텐션을 적용하는 내용을 다룰 예정이다. 또, 그래프 신경망의 결과물인 정점 임베딩으로부터 그래프 임베딩을 얻을 수 있는 그래프 풀링을 다루고 그래프 신경망을 학습 시킬 때 일어날 수 있는 지나친 획일화(Over-Smoothing) 문제를 다루겠다.

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


Graph neural network with attention

Limit of graph neural network

기본 Graph neural network에서는 이웃들의 정보를 동일한 가중치로 평균을 낸다.

image

마찬가지로 Graph convolutional network에서도 단순히 연결성을 고려한 가중치로 평균을 낸다.

image

하지만, 그래프 구조에서는 실제로 대상 정점마다 다른 연결성을 갖거나 다른 영향력을 미치는데 위 두 hidden state의 식을 보면 이 같은 점이 반영되지 않음을 알 수 있다.

이러한 한계점을 극복하고자 제안된 신경망인 Graph Attention Network, GAT에서는 가중치 자체도 학습한다. 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문이다. 가중치를 학습하기 위해서 self-attention을 사용한다.

image

  • 위의 그림에서 볼 수 있듯이, vertex 4에 영향을 미치는 edges마다 서로 다른 가중치들($\alpha$)이 사용되는 것을 확인할 수 있다.


Graph attention networks(GATs)

조금 더 자세히 살펴보도록 하자. 각 층에서 정점 $i$로부터 이웃 $j$로의 가중치 $\alpha_{ij}$는 총 3단계를 통해 계산한다.

  1. 해당 층의 정점 $i$의 임베딩 $\mathbf{h}_i$에 신경망 $\mathbf{W}$를 곱해 새로운 임베딩을 얻는다.

    \[\mathbf{\tilde{h}}_i=\mathbf{h}_i\mathbf{W}\]

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

    \[e_{ij}=\mathbf{a}^\top\left[\text{CONCAT}(\mathbf{\tilde{h}}_i,\mathbf{\tilde{h}}_j)\right]\]

  3. 위 step2의 결과에 소프트맥스를 적용한다.

    \[\alpha_{ij}=\text{softmax}_j(e_{ij})=\frac{\text{exp}(e_{ij})}{\sum_{k\in \mathcal{N}_i}\text{exp}(e_{ij})}\]

여기서 학습에 사용되는 파라미터는 $\mathbf{W}$와 $\mathbf{a}$이다.

transformer의 self-attention layer를 여러개 concat하여 multi-head attention으로 사용하듯, 그래프 구조에서도 여러개의 어텐션을 동시에 학습한 뒤, 결과를 연결하여 사용한다.

\[\mathbf{h}'_i = \underset{1\leq k\leq K}{\text{CONCAT}}\sigma\left(\sum_{j\in\mathcal{N}_i}\alpha_{ij}^k \mathbf{h}_j\mathbf{W}_k\right)\]
  • 위 식에서 볼 수 있듯이, $k$개의 $\alpha$를 얻어 concatenate하여 최종적으로 $\mathbf{h}’_i$를 얻는 것을 볼 수 있다.

image

이러한 방식으로 학습된 GAT는 정점 분류의 정확도를 향상시켰다.

image


Graph representation learning

그래프 표현 학습, 혹은 그래프 임베딩(Node embedding이 아니라 graph embedding임을 주의)은 그래프 전체를 벡터의 형태로 표현하는 것이다.

Node embedding이 정점을 벡터의 형태로 표현하는 것이라면, graph embedding은 벡터로 표현된 그래프 그 자체를 의미하기도 한다. 이러한 그래프 임베딩은 그래프 분류 등에도 활용된다. 그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측하는 것이 한 가지 예시이다.


Graph Pooling

그래프 풀링은 정점 임베딩으로부터 그래프 임베딩을 얻는 과정이다.

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

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

image

  • 먼저 그래프 신경망을 사용해서 정점별 임베딩을 얻고
  • 군집구조를 이용해서 군집별 임베딩을 합산한다.
  • 군집의 군집들을 계속적으로 찾고 합산하여
  • 최종적으로 그래프를 위한 임베딩으로 만들고 이를 classifier에 통과시켜 분류한다.

위 과정에서 그래프 신경망은 총 세 군데에서 사용된다.

  • 정점 임베딩을 얻을 때
  • 군집을 찾을 때
  • 군집 내에서 합산할 때


Over-smoothing Problem

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

over-smoothing 문제는 작은 세상 효과와 관련있다. 즉, 정점간의 거리가 너무 가까운데서 발생하는 문제다. 아래 그림을 예시로 들자면, distance가 5정도면 거의 모든 점들을 cover할 수 있고, 지역적인 정보를 집계하는 것이 아니라 그래프 전반을 집계하게 되어 비슷한 임베딩이 되는 것을 확인할 수 있다.

imageimage

이처럼 over-smoothing의 결과로 그래프 신경망의 층 수를 늘렸을 때, 후속 과제(eq. 분류 task)에서의 정확도가 감소하는 현상을 발견했다.

image

위 그림에서 볼 수 있듯, 그래프 신경망의 layer가 2~3일 때 정확도가 가장 높은 것을 확인할 수 있다. Convolutional layer와 비슷하게 residual 층을 넣는 것을 생각해볼 수 있다. 하지만 이전 layer의 임베딩을 한 번 더 더해주는 residual 층 만으로는 효과가 제한적이다.

\[\mathbf{h}_u^{(l+1)}=\mathbf{h}_u^{(l+1)}+\mathbf{h}_u^{(l)}\]

이러한 over-smoothing 문제를 해결하기 위해 JK 네트워크(Jumping Knowledge Network)가 개발 되었다. JK 네트워크는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용하는 방식이다.

image

순차적으로 layer별 임베딩을 진행 후 마지막 layer의 임베딩만을 사용했던 기존 방식을 버리고, 모든 층의 임베딩을 사용하는 방식이다.

또다른 over-smoothing 문제를 해결하기 위한 방법으로는 APPNP가 있다. 이는 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화한 방식이다. 기존 층에서 층으로 갈 때 학습되던 $\mathbf{W}$를 0번째 층에서만 적용하고 나머지 층에서는 삭제한 뒤 집계함수를 단순화한 방식이다.

image

위의 두 방법 JK네트워크와 APPNP 모두 성능에 효과가 있는 것으로 나타났고, 특히 APPNP의 경우 층의 수가 증가하여도 정확도 감소 효과가 없는 것을 확인하였다고 한다.

image


Graph data augmentation

데이터 증강은 다양한 기계학습 문제에서 효과적이다.

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

image

  • 위 그림의 순서를 1$\rightarrow$2$\rightarrow$3$\rightarrow$4$\rightarrow$GNN 라고 하자
  • 1에서 input graph가 주어지면 이 때 정점간 유사도를 계산하여 edge 형태로 표현한다(2)
  • 2에서 유사도가 높은 edge들만을 필터링하여 3의 형태로 표현한다.
  • 3의 정보를 다시 1의 입력 그래프에 추가하여 4의 간선이 추가된 그래프를 얻고 GNN에 넣는다.

그래프 데이터 augmentation의 결과 정점 분류(node classification)의 정확도가 개선되는 것을 아래와 같이 확인할 수 있다.

image

  • 위의 표에서 Heat와 PPR은 유사도를 계산하는 두 가지 방법이고, 이에 따라 제안된 그래프 데이터 증강 기법을 의미한다.
  • Cora와 Citeseer 데이터에서 다양한 GNN에 대해 두 증강 기법을 사용한 경우가 그렇지 않은 경우(None)에 비해 성능이 개선 되었음을 확인할 수 있다.


Further Reading

Further Questions

  • GraphSAGE 모델에서는 하나의 정점을 나타내기 위하여 집계 함수를 활용합니다. 이때, 자기 자신만의 임베딩 뿐 아니라 이웃 정점의 임베딩까지 사용합니다. 이러한 방식으로 정점을 정의하게 된다면, 어떠한 장점이 있을까?