7. GNN

7.1. General GNN Framework

 

GNN에서 신경써야 할 것들은 다음과 같다.

 

1. Message: Node embedding에서 Message를 어떻게 만들 것인가

2. Aggregration: neighbor들의 Node embedding을 어떻게 모을 것인가

3. Layer connectivity: 1, 2를 가지고 만든 single layer들을 어떻게 연결할 것인가(예: skip connection을 쓸 것인가?)

4. Graph manipulation: node를 augmentation할 것인가?

5. Training objectives: supervised learning Vs. Unsupervised Learning, Node, Edge, Graph level...

 

7.2 Single Layer of GNN

GNN에서 하나의 layer는 다음과 같은 기능을 수행한다.

(1) Message transformation: 이전 node embedding을 변환하는 단계

(2) Message aggregation: neighbor들의 node embedding을 모으는 단계

(3) Activation: aggregation 이후에 nonlinearity를 추가하여 expressiveness를 늘린다.

 

여러가지 GNN을 Message + Aggregation 틀에 맞추어 설명해보자.

 

Graph Convolution Network (GCN)

node embedding에 linear transformation을 취하고, average를 취한다.

원래의 식은 위와 같으나 Message + Aggregation으로 나누어 표현하여 보자.

GraphSAGE

GCN과 GraphSAGE의 가장 큰 차이점은 GCN은 Node 자체의 embedding은 사용하지 않으나 GraphSAGE는 Node 자체의 embedding을 따로 transformation하고, Concat해서 사용한다는 점이다.

전체 식은 위와 같고, aggregation function은 다양하게 정할 수 있다. (Average, Pooling (Mean, Max), 심지어 LSTM으로 할 수도 있다.)

Message + Aggregation 형식으로 표현하면 다음과 같다.

(옵션) embedding의 크기를 맞춰주기 위해 l2 Normalization을 하면 성능이 좋아지기도 한다.

 

Graph Attention Network (GAT)

Graph Attention Network는 GraphSAGE보다는 GCN에 가깝다고 볼 수 있다.

GCN은 Average를 사용하므로 Sum을 할 때 각 Neighbor들의 중요도(weight)는 똑같이 1/degree라고 할 수 있다.

GAT에서는 각 node들의 중요도(weight)를 attention mechanism을 이용해 구한다.(Attention Weight)

 

Attention Mechanism은 자유롭게 정할 수 있는데 보통 두 노드의 임베딩을 Linear + Non-linear layer를 통해서 만들어낸다.

그런 뒤에 weight들의 크기를 맞춰주기 위해 softmax를 취한다.

Attention Mechanism과 Graph Neural Network는 동시에 학습된다.

 

하나의 attention mechanism이 잘 통하지 않는 경우도 있으니 여러개의 attention mechanism을 동시에 사용하고 aggregation하기도 한다.

다음과 같은 장점들이 있다고 한다.(아직 와닿지 않는다.)

- Computationally efficient

- Storage efficient

- Localized

- Inductive capability

 

Modern Deep learning Techniques

이 외에도 딥러닝에 쓰이는 테크닉들을 쓸 수 있다.

- Batch Norm: 노드들의 크기를 Normalize한다. (여기서 말하는 Batch는 무엇일까?)

- Dropout: Message Transformation의 Linear layer에 적용 가능

- Activation: 다양한 activation function 사용 가능

 

7.3 Stacking Layers of a GNN

이전 시간에 GNN layer 하나를 어떻게 구성하는지 배웠으니 이러한 layer들을 연결하는 법을 알아보자.

 

CNN과는 다르게 GNN에서는 layer의 개수가 반드시 더 많은 expressiveness를 의미하지 않는다.

다만, information을 얼마나 많은 hop에서 얻느냐를 말한다.

# of GNN layers = # of hops != expressiveness

 

over-smoothing problem

GNN layer를 너무 많이 사용하면 node embedding이 전부 비슷해지는 현상이 생기는데 이를 over-smoothing problem이라고 부른다.

이는 hop이 커지면 reception field가 커져서 결국에는 비슷한 노드를 사용하기 때문에 만들어지는 일이다.

아래 그림을 보면 3-hop만 지나도 그래프의 대부분의 node를 커버하게 된다.

 

따라서 다른 Deep learning과는 달리 GNN은 Layer를 늘리는 것이 반드시 좋은 것(expressiveness를 늘리는 것)은 아니다.

 

GNN Layer를 적게 쓰면서 expressiveness를 늘리는 방법은 다음과 같다.

(1) GNN layer 내의 linear layer를 늘리기 (예: message transformation에 쓰이는 MLP layer)

(2) GNN layer 들을 쓰기 전이나 후에 쓰는 MLP layer를 늘이기

 

혹은 GNN layer들에 skip connection을 사용하면 된다.

Skip connection은 node 자체의 정보를 보존하는데 큰 도움을 주기 때문에 receptive field가 커져도 node embedding이 비슷해지지 않도록 해준다. (Shallow network와 Deep network를 같이 쓰는 효과)

Skip connection은 activation function 전에 node embedding 자체를 더해줘서 만들 수 있다.