7. Graph Neural Networks 2: Design Space

GNN Tobigs·2021년 8월 25일

CS224W GNN

작성자: 이정은

1. A General GNN Framework

슬라이드1

위 그림과 같이 일반적인 GNN의 framework는 다음과 같고, GNN을 디자인하는 방법을 총 5가지로 나눠서 볼 수 있습니다. 오늘 강의에서는 이 중 3단계까지에 대해서만 다룹니다. 간단하게 설명하자면

GNN Layer = Message + Aggeration은 핵심적인 요소로 이 과정을 어떻게 하느냐에 따라서 GCN, GraphSAGE, GAT 등의 GNN 그래프 종류가 나눠집니다.
Layer Connectivity: 어떻게 multi layer를 쌓을건지를 결정하는 부분으로, 일반적으로 sequential하게 층을 쌓고 옵션으로 skip connection도 추가할 수 있습니다.

2. GNN Layer

슬라이드2

단일 GNN layer에서는 이전 계층에서 넘어 온 하위 벡터 집합의 Message Computation을 진행하고, 나온 결과들을 Message Aggeration 과정을 거쳐 하나의 단일 벡터로 압축시킵니다.

2-1. Message Computation

m_u^{(l)} = MSG^{(l)}(h_u^{(l-1)})

Message 함수( $MSG$ )는 이전 계층에서 넘어온 각 노드의 정보, 표현을 transform하여 다음 층으로 보낼 message를 만들어냅니다.

m_u^{(l)} = W^{(l)}h_u^{(l-1)}

예시로 weight matrix $W$ 를 함수로 사용하여 노드 feature와 곱하여 linear하게 변형하는 방법이 있습니다.

2-2. Aggregation

h_v^{(l)} = AGG^{(l)}(\{m_u^{(l)}, u \in N(v)\})

Aggregation은 특정 노드 v가 있을 때, 이의 이웃 노드들인 u의 메세지를 모두 집계하여 하나의 벡터로 압축시키는 과정입니다. Aggerator로 쓰이는 함수( $AGG$ )에는 대표적으로 $Sum(\cdot), Mean(\cdot), Max(\cdot)$ 가 있고 이는 모두 permutation invariant한 순서에 영향을 받지 않는 함수라는 특징이 있습니다.

Issue

위와 같은 Aggregation 과정을 거치면 노드 v의 이웃 노드들에 대한 정보만 계산되어 $h_v^{(l)}$ 가 $h_v^{(l-1)}$ 에 직접적으로 의존하지 않습니다. 따라서 노드 v 자기 자신에 대한 정보가 소실되는 문제가 발생합니다.

이를 해결하는 방법은 $h_v^{(l)}$ 계산에 $h_v^{(l-1)}$ 값을 포함하는 것입니다.

m_u^{(l)} = W^{(l)}h_u^{(l-1)}

m_v^{(l)} = B^{(l)}h_v^{(l-1)}

Message computation 할 때에는 자신 노드와 이웃 노드들에 다른 함수를 사용합니다.

h_v^{(l)} = CONCAT(AGG^{(l)}(\{m_u^{(l)}, u \in N(v)\}), m_v^{(l)})

Aggregation은 기존 방식과 동일하게 이웃 노드들의 message를 집계한 이후에 자기 자신에서온 message를 concatenation 혹은 summation으로 집계합니다.

2-3. Activation Function

Message와 Aggregate 과정은 모두 선형 함수입니다. 따라서 비선형성을 더해주기 위해 activation function을 통과시킵니다. 이 과정은 더 좋은 표현력을 만들어주기 때문에 매우 중요한 과정입니다. $\sigma(\cdot)$ 로 주로 쓰이며, $ReLU(\cdot), Sigmoid(\cdot)$ 등의 함수가 있습니다.

3. Classic GNN Layers

Message Computation과 Aggregation에 따른 몇 가지 중요한 GNN 모델을 살펴보고자 합니다.

3-1. GCN(Graph Convolutional Networks)

GCN은 지난 강의에서도 다뤘던 가장 기본적인 GNN 모델입니다.

h_v^{(l)} = \sigma( \sum_{u \in N(v)} W^{(l)}\frac{h_u^{(l-1)}}{|N(v)|})

해당 수식을 message와 aggregation으로 나눠서 살펴보면

m_u^{(l)} = \frac{1}{|N(v)|}W^{(l)}h_u^{(l-1)}

각 노드의 메세지는 node degree로 normalize를 진행합니다.

h_v^{(l)} = \sigma(Sum(\{m_u^{(l)}, u \in N(v)\}))

노드 v의 이웃 노드 u의 메세지를 합산하고, 활성 함수를 거칩니다.

3-2. GraphSAGE

GraphSAGE는 GCN을 기반으로 확장된 모델로, aggregation에서 차이점을 가집니다.

h_v^{(l)} = \sigma(W^{(l)} \cdot CONCAT(h_v^{(l-1)}, AGG(\{h_u^{(l-1)}, \forall u \in N(v)\})))

Message는 $AGG(\cdot)$ 내에서 계산되고, aggregation은 두 가지 과정을 거칩니다.

h_{n(v)}^{(l)} \leftarrow AGG(\{h_uh_v^{(l-1)}, \forall u \in N(v)\})

GraphSAGE에서의 $AGG$ 는 단순 합계뿐만 아니라 다양한 함수를 사용할 수 있습니다.

h_v^{(l)} \leftarrow \sigma(W^{(l)} \cdot CONCAT(h_v^{(l-1)}, h_{N(v)}^{(l)}))

그리고 이웃 노드들의 계산 결과와 이전 계층의 자기 자신에 대한 정보를 concat하여 활성 함수를 거칩니다.

3-2-1. Neighbor Aggregation

GNN2

$AGG$ 종류에는 크게 3가지가 있습니다.

Mean: GCN과 동일한 방법으로, 이웃들의 가중 평균값을 구합니다.
Pool: Message computation으로 MLP를 사용하여 non-linear하게 만들고, 이를 Mean 혹은 Max하여 집계를 도출해냅니다.
LSTM: 이웃들로부터 오는 Message sequence model에 LSTM을 사용할 수 있습니다. 다만, sequence model은 order invariant하지 않으므로 훈련할 때 이웃들의 순서를 resuffle해야 합니다.

3-2-2. L2 Normalization

추가로 모든 layer의 임베딩 벡터에 L2 normalization을 적용할 수 있습니다.

h_v^{(l)} \leftarrow \frac{h_v^{(l)}}{\parallel h_v^{(l)} \parallel _2} where \parallel u \parallel _2 = \sqrt {\sum_{i} u_i^2} (l_2 -norm)

이를 진행하면 모든 벡터는 같은 l2-norm 즉, 길이가 1인 벡터가 됩니다. 기존 임베딩 벡터의 크기나 길이가 많이 다른 경우에는 정규화를 하고 나면 성능이 향상됩니다.

3-3. GAT(Graph Attention Networks)

GAT는 이웃 노드에 대한 중요도를 나타낸 attention weights를 추가한 모델입니다.

h_v^{(l)} = \sigma(\sum_{u \in N(v)} \alpha _{vu} W^{(l)}h_u^{(l-1)})

해당 식에서 $\alpha _{vu}$ 는 노드 v로 오는 노드 u의 message에 대한 중요도를 나타냅니다.

기존 GCN과 GraphSAGE에서는 중요도를 $\alpha _{vu} = \frac{1}{|N(v)|}$ 즉, node degree로 나눠서 표현했다고 볼 수 있습니다. 이렇게 되면 중요도는 노드 u에 상관없이 노드 v에만 의존하여 이웃 노드 u는 모두 같은 중요도를 가지게 됩니다.

그러나 모든 이웃들은 같은 중요도를 갖고 있지 않습니다. 따라서 attention weight는 중요한 부분에 포커스를 맞추고 나머지는 fade out 시켜, 신경망이 중요한 곳에 컴퓨팅 파워를 쏟을 수 있게 합니다. 어떤 부분이 중요한지는 다 다르기 때문에 attention weight는 훈련을 통해 학습됩니다.

3-3-1. Attention Mechanism

Attention mechanism $\alpha$ 를 가지고 attention weight $a_{vu}$ 를 계산합니다. 전체적인 과정은

e_{vu} = \alpha (W^{(l)}h_u^{(l-1)}, W^{(l)}h_v^{(l-1)})

먼저, 노드 u, v의 message를 기반으로 두 노드의 attention coefficients $e_{vu}$ 를 계산합니다. 이때 $e_{vu}$ 는 노드 v로 오는 노드 u의 message에 대한 중요도를 나타냅니다.

a_{vu} = \frac{exp(e_{vu})}{\sum_{k \in N(v))} exp(e_{vk})}, that \sum_{u \in N(v))} \alpha _{vu}=1

그리고 정규화시킨 $e_{vu}$ 를 final attention weight $\alpha _{vu}$ 에 넣습니다. 이때 softmax 함수를 사용하여 노드 v에 대한 모든 $\alpha _{vu}$ 의 합은 1이 됩니다.

GNN2-3

h_v^{(l)} = \sigma(\sum_{u \in N(v)} \alpha _{vu} W^{(l)}h_u^{(l-1)})

최종적으로 final attention weight $\alpha _{vu}$ 을 기반으로 weighted sum을 합니다.

GNN2-10

Attension mechanism $\alpha$ 가 simple single-layer nueral network라고 했을 때, 파라미터 a는 weight matrix $W^{(l)}$ 와 함께 end-to-end로 학습됩니다.

3-3-2. Multi-head Attention

GNN2-4

Multi-head attention은 각각 다른 파라미터 즉, 다른 attention coefficient로 여러 개의 $h_v^{(1)}[N]$ 을 구해서 이를 aggregation해 최종 $h_v^{(1)}$ 로 사용합니다.

기존 attention에서 $\alpha$ 를 랜덤하게 초기화시키면 local minimum에 빠져 학습과 수렴에 문제가 발생할 수 있습니다. multi-head attention은 각각의 $\alpha$ 를 다 합치기 때문에 모델을 robust하고 stabilize하게 바꿔 이러한 문제를 해결할 수 있습니다.

3-3-3. Benefits of Attention Mechanism

Attention Mechanism의 주된 benefit은 서로 다른 이웃에 대해 다른 중요도를 지정할 수 있다는 것입니다. 이는 추가적으로 다음과 같은 이점을 가집니다.

Computatiionally efficient: 모든 엣지에 대해 병렬 계산이 가능하고, 모든 노드에 대해 병렬적으로 aggregation이 가능합니다.
Storage efficient: sparse matrix에는 O(V+E) 이상은 저장되지 않고, 그래프의 크기에 상관없이 파라미터의 개수가 고정되어 있습니다.
Localized: local network neighborhoods에만 의존합니다.
Inductive capability: edge-wise mechanism과 공유가 가능하고, 이는 global graph structure에는 의존하지 않습니다.

3-4. GNN Layer in Practice

GNN2-1

더 좋은 성능을 내기 위해 GNN layer를 디자인할 때, modern deep learning modules를 포함시킬 수 있습니다.

3-4-1. Batch Normalization

GNN2-2

Batch Normalization은 노드 임베딩의 batch마다 평균이 0, 분산이 1이 되게 정규화를 진행합니다. 이는 신경망 훈련을 안정적으로 할 수 있게 합니다.

3-4-2. Dropout

슬라이드5

Dropout은 훈련 시 신경망을 regularize하여 더 robust하게 만들고 overfitting을 방지할 수 있습니다. 훈련할 때에는 확률 p만큼 랜덤하게 뉴런을 0으로 바꿔 사용하지 않고, 테스트 시에는 모든 뉴런을 사용합니다.

GNN에서의 dropout은 message function의 linear layer에 적용됩니다. 따라서 message computation을 거치고 나면 dropout이 진행되어 있는 형태가 됩니다.

3-4-3. Activation Function(Non-linearity)

슬라이드6

앞서 계속 했듯이 message computation과 agggregation을 거쳐 나온 임베딩 벡터에 activation function을 더해 non-linear하게 만들 수 있습니다. 주로 쓰이는 함수로는 $ReLU, Sigmoid, Parametric ReLU$ 가 있는데, 이 중 Parametric ReLU는 ReLU보다 더 좋은 성능을 냅니다.

요약하자면 modern deep learning modules를 GNN layer에 포함시켜 더 좋은 성능을 내는 GNN layer를 디자인할 수 있습니다. 이 분야는 아직도 활발히 연구 중에 있습니다.

4. Layer Connectivity

GNN2-5

기본적으로 GNN layer는 sequencial하게 연결합니다. 특정 노드 feature $x_v$ 가 input으로 들어오면 연결된 GNN layer들을 거쳐 노드 임베딩 $h_v{(L)}$ 이 ouput으로 출력됩니다.

4-1. Too many GNN Layers

4-1-1. Over-smoothing Problem & Receptive Field

너무 많은 개수의 GNN layer를 쌓다보면 over-smoothing 문제가 발생합니다. 이는 모든 임베딩이 같은 값으로 수렴하게 되는 것을 말합니다.

GNN2-6

K-layer GNN의 각 노드는 K-hop neighborhood의 receptive field를 가지게 되는데 이게 깊어지면 깊어질수록 GNN 거의 대부분을 포함하게 됩니다.
임베딩은 receptive filed에 속한 노드들에 의해 결정되기 때문에 그림과 같이 두 노드가 high-overlapped receptive field를 갖는다면 거의 동일한 임베딩 값을 갖게 됩니다.

그렇다면 over-smoothing을 어떻게 해결할 수 있을까?

즉, GNN에서는 층이 많다고해서 꼭 좋은 결과를 내지는 않는다는 것을 알 수 있습니다.
따라서 층의 개수를 너무 많지 않도록 그래프의 직경 등 문제를 해결하는데 필요한 receptive field를 구해내고, 이보다 조금 더 많은 수를 GNN layer 개수로 설정합니다.

4-2. Shallow GNN Layers

반대로 레이어의 개수가 너무 적을 때, GNN의 표현력을 높이는 방법으로는 크게 두 가지가 있습니다.

첫 번째로 message transformation과 aggregation을 deep neural network로 바꾸는 것입니다. 이렇게 되면 기존의 single layer가 3-layer로 바뀌게 됩니다.

슬라이드9

두 번째는 GNN layer의 앞 뒤로 MLP layer를 추가하는 방법입니다. Pre-processing layer는 노드 feature를 인코딩할 때 중요한 역할을 하고, Post-preprocessing layer는 노드 임베딩을 가지고 추론하거나 변환할 때 중요한 역할을 합니다. 실제로 이렇게 레이어를 추가하는 방법은 더 좋은 표현을 만들어 냅니다.

4-2-1. Skip Connection

만약 위 방법들을 사용해도 아직 레이어의 개수가 부족하다면, skip connection을 추가합니다.

GNN2-7

우리는 이전 계층의 노드 임베딩이 노드를 더 잘 구별할 수 있다는 것을 알았기 때문에, skip connection을 추가하여 이전 계층이 최종 임베딩에 끼치는 영향을 증가시킵니다.

GNN2-8

Skip connection은 이전 계층과 현재 계층을 weight combination하여 혼합 모델을 만듭니다. N개의 skip connection이 있을 때, 모델은 총 $^N$ 개가 생성되고, 얕은 층의 GNN과 깊은 층의 GNN이 자동으로 혼합되어 표현을 더 효과적으로 생성해낼 수 있습니다.

GNN2-9

이를 수식으로 나타내면 왼쪽과 같습니다.
그리고 만약 마지막 계층으로 skip connection을 진행한다면, 최종 계층은 이전 계층의 모든 노드 임베딩에서 직접 aggregate하게 됩니다.

Summary

Design GNN framework

GNN Layer: Message Computation + Aggregation
- Classic GNN Layer: GCN, GraphSAGE, GAT
- Deep Learning Modules
Layer Connectivity
- Too many layers: Over-smoohting problem & Receptive filed
- Shallow layers: Add layer / Skip Connection

GNN Tobigs

투빅스 1415기 GNN 스터디입니다.

이전 포스트

6. Graph Neural Networks 1: GNN Model

다음 포스트

7. Graph Neural Networks 2: Design Space

3개의 댓글

김상현

2021년 8월 31일

14기 김상현

GNN layer는 message computation, aggregation, activation function으로 구성된다.
GNN layer의 종류
 GCN
 GraphSAGE: GCN 기반으로 확장된 모델로 mean, pool, lstm 등 다양한 aggregation을 사용하며 L2 normalization을 적용
 GAT: attention mechanism을 사용하며 robust하고 stabilize를 위해 multi head attention 사용한다. GAT의 이점은 computationally efficient, storage efficient, localized, inductive capability 등이 있다.
GNN layer들이 많은 경우
 Over-smoothing problem: 모든 임베딩이 같은 값을 수렴하는 문제
 층의 개수를 너무 많지 않도록 필요한 receptive field를 구한 후 네트워크 개수를 설정
GNN layer가 얕은 경우
 GNN 전, 후로 mlp layer를 추가한다
 Skip connection을 사용한다.

GNN design에 대해 이해할 수 있었습니다.
유익한 강의 감사합니다 :)

답글 달기

이성범

2021년 9월 1일

[15기 이성범]

GNN 모델은 Message와 Aggregation 함수가 어떠한 방식으로 이루어지냐에 따라서 종류가 달라진다.

Message 함수는 말 그대로 이전 계층에 넘어온 각 노드의 정보를 어떻게 보낼지에 대하여 결정하는 함수이고, Aggregation 함수는 들어온 메세지들을 어떻게 합칠지에 대하여 결정하는 함수이다.

Graph Convolutional Networks은 가장 기본적인 GNN 모델로 각 노드의 메세지를 node degree로 정규화 하고, 현재 노드와 이웃노드의 정보를 sum을 통하여 합산하고 활성화 함수를 거친다.

GraphSAGE는 GCN을 기반으로 확장된 모델로 aggregation에서 차이점을 가진다. 각 노드의 메세지는 AGG 내에서 계산되는데 AGG의 경우 단순 sum 뿐만아니라 다양한 함수를 사용할 수 있다. 그리고 현재 노드와 이웃 노드의 정보를 concat하여 활성화 함수를 거친다.

Graph Attention Networks는 이웃 노드에 대한 중요도를 나타내는 attention weights를 추가한 모델이다. 기존 GCN과 GraphSAGE에서는 중요도를 node degree로 나눠서 표현했다고 볼 수 있는데, 이렇게 된다면 중요도는 노드 u에 상관없이 노드 v에만 의존하여 이웃 노드 u는 모두 같은 중요도를 가지게 된다.
그러나 모든 이웃들은 같은 중요도를 갖고 있지 않다. 따라서 attention weight는 중요한 부분에 포커스를 맞추고 나머지는 fade out 시켜, 신경망이 중요한 곳에 컴퓨팅 파워를 쏟을 수 있게 한다.

GNN에서 Layer를 무작정 깊게 쌓게 된다면, 모든 임베딩이 같은 값으로 수렴하게 되는 over-smoothing 문제가 발생한다.
따라서 효과적으로 Layer를 쌓는 것이 중요하다. 그 방법으로는 총 3가지가 있다. 첫 번째로 message transformation과 aggregation을 deep neural network로 바꾸는 것, 두 번째는 GNN layer의 앞 뒤로 MLP layer를 추가하는 방법, 이전 계층과 현재 계층의 weight를 combination 하는 Skip connection을 활용하는 방법이다.

답글 달기

Yeeun Jang

2021년 9월 3일

GNN을 디자인하는 5단계 중 3단계
Message와 Aggregation 과정에 따라서 GNN 그래프의 종류가 나눠진다.
(1) Message computation (GNN layer) : 이전 계층에서 넘어온 노드의 정보, 표현을 다음 층으로 보낼 메세지로 만듦 (ex - linear)
(2) Aggregation (GNN layer) : 이웃 노드의 메세지를 집계해서 하나의 벡터로 압축 (aggregate)
(3) Layer connectivity : 여러개의 레이어를 쌓는 방법. sequential 또는 skip connection
Classic GNN

GCN : 가장 기본적
GraphSAGE : GCN과 agg부분 다름, neighbor agg (mean, pool, LSTM), L2 norm 등 사용
GAT : 이웃 노드의 중요도를 attention weight를 통해 반영, weight는 훈련을 통해 학습

더 좋은 성능을 내기 위한 방법

Batch normalization 2. Dropout 3. Activation function 4. Layer connectivity

레이어 수가 너무 많을 때 (over smoothing 문제)
레이어 수가 많으면 거의 모든 노드가 receptive field가 되는 문제 => receptive field가 거의 동일해 over smoothing 문제
레이어 수가 너무 적을 때 ( 표현력 저하)
message, agg 부분을 NN으로 변경 => 한 레이어가 더 깊어짐(3 layer)
Skip connection 추가해서 레이어 늘림

답글 달기