Graph Neural Network (GNN)

Node Embedding

정점 임베딩(Node Embedding)은 주어진 그래프에서 각 정점을 벡터 표현으로 변환하는 것이다.

그래프에서 정점간 유사도를 임베딩 된 벡터 공간에서 보존하는 것을 목표로 임베딩 한다.

 

Node Embedding

인접성/거리/경로/중첩/랜덤워크 기반 접근법으로 similarity를 정의한다.

 

위의 정점 임베딩 방식은 학습의 결과로 임베딩된 정점의 벡터를 얻게 되는 Transductive(변환식) 방법이다.

변환식 정점 표현 방식은 학습이 진행된 후, 추가 정점에 대한 임베딩을 얻을 수 없으며 정점의 속성(Attribute) 정보를 활용할 수 없으며 모든 정점에 대한 임베딩을 저장할 공간이 필요하다는 문제점이 있다.

 

변환식 방법의 한계는 학습의 결과로 정점을 임베딩 시키는 인코더를 얻는 귀납식 임베딩 방법을 사용하여 해결할 수 있다.

 

GNN은 대표적인 귀납적 임베딩 방법이다.

 

GNN

GNN은 그래프와 정점의 속성 정보(Attribute)를 입력으로 받는다.

 

그래프의 정보 A는 |V| x |V| 형태의 이진행렬인 인접 행렬로 받는다.

각 정점 u의 속성 벡터 $X_{u}$는 m차원의 벡터로 m은 속성의 수를 의미한다.

정점의 속성의 예시는 소셜 네트워크에서 지역, 성별, 연령 등이다.

 

GNN

 

GNN은 대상 정점의 이웃들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.

 

 

위와 같이 0번 층에서 input으로 각 정점의 속성 벡터를 사용하여 층마다 새로운 임베딩을 얻고 이를 다시 다음 층의 input으로 사용한다.

모든 정점을 대상 정점으로 사용하지 않더라도 모든 정점에 대한 임베딩을 얻을 수 있다.

 

대상 정점에 따른 계산그래프

대상 정점에 따라 계산그래프는 다르게 형성되는데 이때 같은 층은 모두 같은 weight를 사용하며 모든 계산 그래프에서 같은 층의 weight를 공유한다.

 

계산 그래프의 특성상 그래프의 이웃의 수에 따라 input의 수가 달라지는데 이는 집계 함수를 통해 하나로 압축시킨다.

집계 함수는 이웃들 정보의 평균을 계산하여 신경망에 계산한 값을 input으로 넣는다.

 

N(v)는 정점 v의 이웃의 집합이다.

위의 수식을 통해 계산된 마지막 층의 임베딩 $z_{v} = h_v^{K}$가 정점 v의 출력 임베딩이 된다.

$W_{k}$와 $B_{k}$는 층 별 신경망의 가중치로 학습되어야 할 learning parameters다.

 

 GNN Loss Function

Loss Function은 위와 같이 모든 정점 쌍에 대해 임베딩 공간에서 유사도와 그래프에서 유사도의 차의 제곱을 합하여 계산 된다.

 

Semi-Supervised 방식이 아닌 후속 과제에 대한 손실 함수를 활용하여 End-To-End 학습도 가능하다.

정점의 임베딩을 활용하여 분류를 하는 것이 후속 과제라면 바로 다음과 같이 Loss Function을 설정할 수 있다.

 

Binary Classification Loss

 

Graph Convolutional Network (GCN)

 

그래프 합성곱 신경망은 다음과 같은 집계 함수를 사용한다.

 

GCN 집계 함수

GNN vs GCN

GNN의 기존 집계 함수와 차이점은 대상 정점의 전 층의 임베딩 값을 학습 가능한 Weight $B_{k}$와 내적 되어 사용하였는데 이를 제거하고 하나의 신경망으로 학습 변수를 공유한다,

정규화 방법 또한 변화하였다.

 

GraphSage

GraphSage는 다른 집계 함수를 사용하는 GNN으로 정점의 이웃들의 임베딩을 AGG 함수를 통해 합치고 자신의 전 층에서의 임베딩과 연결하여 현재 층에서 대상 정점의 임베딩 벡터를 계산한다.

 

GraphSage 집계 함수

GraphSage AGG func

GraphSage의 AGG 함수로는 Mean, Pool, LSTM 등 여러 함수가 사용된다.

 

Graph Attention Network (GAT)

기존 그래프 신경망은 이웃들의 정보를 모두 동일한 가중치로 평균을 계산한다.

그래프 합성곱 신경망에서도 이는 동일하다.

하지만 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있다.

이를 반영하기 위해 Self-Attention을 사용한다.

 

GAT는 다음과 같은 단계로 이루어져 있다

 

GAT Mechanism

Multi-Head Attention 또한 적용할 수 있으며 정확도의 향상을 보인다.

 

Graph Embedding

그래프 표현 학습(Graph Embedding)은 그래프 전체를 벡터로 표현하는 것이다.

그래프 임베딩을 통해 그래프 분류와 같은 Task를 수행할 수 있다. (ex 화합물 분자 구조 그래프 -> 특성 예측)

 

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

평균과 같이 단순한 방법보다 그래프의 구조를 고려한 풀링과 같은 방법을 사용하면 그래프 분류 등 후속 과제에서 더 좋은 성능을 기록한다.

 

Graph Pooling

 

Over-smooting(지나친 획일화) 문제는 그래프의 신경망이 깊어지면 정점의 임베딩이 모두 유사해지는 현상이다.

적은 수의 층으로도 작은 세상 효과에 의해 다수의 정점이 영향을 받기 때문이다.

 

Over-smoothing

Residual connection을 적용하여 잔차항을 넣어, 이전 층의 임베딩을 한번 더 더해주는 것으로 조금의 Over-smoothing문제를 해결할 수 있으나 전체 네트워크 구조의 수정이 필요하다.

 

Jumping Knowledge Network (JK Network)

 

JK Network

모든 층의 임베딩 벡터를 사용하여 대상 정점의 마지막 출력 임베딩을 계산하는 JK Network

 

APPNP

APPNP(The approximate personalized propagation of neural predictions)는 처음 0번째 층을 제외하고 신경망을 사용하지 않은 집계 함수를 사용한다.

 

APPNP Structure

APPNP의 경우 임베딩 층이 깊어져도 후속 과제를 수행하는데 성능이 저하하지 않음이 확인되었다.

 

그래프 데이터에서도 Data Augmentation을 적용하여 유사도가 높은 정점 간에 간선을 추가하여 후속 과제의 정확도를 개선할 수 있다.

 

Reference

[1] Naver Boostcamp AI-Tech GNN기초 & GNN 심화 (신기정 교수님)