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

김경준·2022년 4월 4일

CS224W Graph study

0

CS224W

목록 보기

7/17

1. A general Perspective on GNNs

A General GNN Framework

하나의 GNN layer는 message와 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
$m_{u}^{(l)}=M S G^{(l)}\left(h_{u}^{(l-1)}\right)$
이전 레이어의 정보가 message function을 통과해 현재 레이어의 정보가 된다.
Aggregation
$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을 적용하는 방법도 있다.
$e_{uv}$ 는 중심노드 $v$ 에 대한 이웃노드 $u$ 의 절대 중요도로 일반적으로 message transformatin한 두 노드를 concat한 후 선형변환하여 얻는다.
$a_{uv}$ 는 상대 중요도로 소프트맥스를 취해 얻을 수 있다. $\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을 활용할 수 있다.
$N$ 개의 skip connection을 쓰면 $2^N$ 개의 paths가 만들어져 적은 레이어만 통과하는 shallow model처럼 작동하기도, 많은 레이어를 통과하여 deep model처럼 작동하기도 한다.
Skip connetion은 자신의 레이어를 skip하도록 구성할수도 있으며 위와 같이 곧바로 출력으로 skip하도록 구성할수도 있다.

References

이전 포스트

<CS224W> Lecture 6. Graph Neural Networks 1: GNN Model

다음 포스트

<CS224W> Lecture 8. Applications of Graph Neural Networks

0개의 댓글