<CS224W> Lecture 7. Graph Neural Networks 2: Design Space

kimkj38·2022년 4월 4일
0

CS224W

목록 보기
7/17

1. A general Perspective on GNNs

A General GNN Framework

  • 하나의 GNN layermessage와 aggregation으로 구성된다.
  • GNN layer는 여러개 쌓을 수 있다.
  • Raw input graph와 computational graph는 다르다. 즉, 여러개의 그래프가 활용될 수 있다.
  • Supervised/ Unsupervised, Node/Edge/Graph level 등을 고려한 objective를 통해 학습한다.

2. A Single Layer of a GNN

Components of A Single Layer

  • Message와 Aggregation이라는 두 스텝을 거쳐 벡터 집합을 single vector로 압축시킨다.
  • Message function
    mu(l)=MSG(l)(hu(l1))m_{u}^{(l)}=M S G^{(l)}\left(h_{u}^{(l-1)}\right)
    이전 레이어의 정보가 message function을 통과해 현재 레이어의 정보가 된다.
  • Aggregation
    hv(l)=AGG(l)({mu(l),uN(v)})h_{v}^{(l)}=A G G^{(l)}\left(\left\{m_{u}^{(l)}, u \in N(v)\right\}\right)
    message function을 통해 변환된 정보를 종합하는 함수 또한 필요하다. 이웃 노드 간에는 순서가 없으므로 평균, 최댓값 등과 같은 order invariant한 함수가 적합하다.
  • Nonlinearlity
    합쳐진 정보는 최종적으로 ReLU나 Sigmoid 같은 비선형 함수를 통과시킨다.

Issue

  • 위 과정에서는 중심 노드가 무엇인지 알 수 없다는 문제가 있다.
  • 이를 해결하기 위한 두가지 해결책이 있다.
    1. Message function을 통과할 때 서로 다른 가중치를 적용한다.
    2. Aggregation 과정에서 이웃 노드들만 연산을 하고 중심노드는 concatenation을 통해 그대로 전달한다.

GCN(Graph Convoluntional Network)

  • Message는 중심노드의 degree로 normalization을 한 후 선형변환한다.
  • Aggregation은 message transform을 거친 모든 이웃 노드들의 정보를 더해준다.

GraphSAGE

  • Aggregation 과정에서 중심노드와 주변노드가 다르게 처리된다.
  • 중심노드는 aggregation 함수를 거치며 중심노드는 agg를 거친 이웃노드들과 concatenation 된다.
  • Aggregation 함수로는 mean, pool, LSTM 등의 방식을 쓴다.
  • 각 레이어의 output에는 L2norm을 취해 normalization을 해준다.

GAT(Graph Attention Networks)

  • 이웃노드에 따라 그 중요도가 다를 수 있기 때문에 attention을 적용하는 방법도 있다.
  • euve_{uv}는 중심노드 vv에 대한 이웃노드 uu의 절대 중요도로 일반적으로 message transformatin한 두 노드를 concat한 후 선형변환하여 얻는다.
  • auva_{uv}는 상대 중요도로 소프트맥스를 취해 얻을 수 있다. uN(v)αvu=1\sum_{u \in N(v)} \alpha_{v u}=1이 된다.
  • 위와 같은 방식으로 attention을 구하는 것은 잘 수렴하지 못하기 때문에 multi attention score를 사용해 학습을 안정화시킨다.
  • 최종적인 임베딩 벡터는 각 임베딩 벡터를 concat하거나 summation하여 구한다.

3. Stacking GNN Layers

Over-Smoothing Problem

  • GNN에서의 깊은 레이어란 중심노드에서 더 많은 hop의 정보를 가져오는 것을 의미한다.
  • GNN의 layer를 깊게 쌓을 경우 모든 노드의 임베딩이 같은 값으로 수렴하는 over-smoothing problem이 나타날 수 있다.
  • Hop의 수가 늘어나면 overlap되는 receptive field가 빠르게 증가하며 노드의 임베딩은 receptive field에 의해 정의되므로 모든 노드들이 다수의 공유되는 노드들로부터 정보를 받는다면 임베딩 벡터가 같아질 수 밖에 없다.

Solution

Do not Stack

  • 레이어를 적게 쌓으면 over-smoothing 문제는 해결할 수 있지만 모델의 표현력이 떨어질 수 있다.
  • Message transformation과 Aggregation function 또한 딥러닝 혹은 affine 변환 레이어이므로 이를 깊게하여 표현력을 향상시킬 수 있다.
  • 혹은 GNN Layer 전후에 message를 통과하지 않는 레이어(ex.MLP)를 추가한다.

Skip Connection

  • GNN layer를 깊게 쌓고 싶다면 skip connection을 활용할 수 있다.
  • NN개의 skip connection을 쓰면 2N2^N개의 paths가 만들어져 적은 레이어만 통과하는 shallow model처럼 작동하기도, 많은 레이어를 통과하여 deep model처럼 작동하기도 한다.
  • Skip connetion은 자신의 레이어를 skip하도록 구성할수도 있으며 위와 같이 곧바로 출력으로 skip하도록 구성할수도 있다.

References

0개의 댓글