Graph Representation Learning - (2) Node Embedding & Basic GNN

Node Embedding

 

그래프 데이터에서 node 를 임베딩하는 방법에는 다양하게 있습니다.

노드 임베딩이란 , 그래프는 일반적으로 non-euclidean space 에 존재하는데 이를 그래프안에 있는 각 노드들을 euclidean space (저차원공간) 에 임베딩해주는것 입니다. 그러면 노드임베딩의 목표는 , 유사한 노드는 embedding space 에서 근처에 위치하게 임베딩해주는 것 입니다.

 

Node Embedding 에는 크게 두가지 방법이 있습니다.

• Shallow embedding method : Node2Vec , DeepWalk , LINE , ... 
• Neural net-based method 

 

Shallow Embedding Method

 

DeepWalk (KDD 2014)

 

Shallow embedding method 에서는 노드임베딩을 위해 다음과 같은 두 노드의 similarity 를 고려합니다.

1. 두 노드의 연결성
2. 두 노드의 이웃 공유 여부
3. 두 노드의 구조적 역할
4. dot product

 

 

 

그러면 Shallow Embedding method 에서는 Node Similarity 를 학습하기 위해 어떻게 최적화를 할까요? 

그 방법을 바로 Random Walks 라고 합니다.

 

Random Walk 알고리즘이란 , 바로 노드 위를 랜덤하게 선택해서 이동하는 것 입니다.

랜덤하게 neighborhood 를 선택해서 거쳐가는 point sequence 로 이용합니다.

(여기서는 Shallow embedding 은 상세히 설명하진 않겠습니다.)

 

 

 

Neural Message Passing : Neural net-based Node Embedding 

 

 

 

 

 

 

GNN 의 기본원리 : Input 그래프 내에서 인접한 노드들을 기반으로 Node Embedding 을 합니다.

이웃한 노드(neighborhood) 들의 노드 정보를 하나로 합치고 이를 matrix 와 곱한 후 Non-linear function 을 통과시킵니다.

그리고 이 과정을 Aggregation 이라고 합니다. 마치 일반적인 Neural net 에서 하나의 hidden layer 를 거치는것과 유사합니다.

 

이 Aggregation 하는 방법의 차이에 따라 GCN , GAT 등으로 달라집니다. 

 

Aggregation 은 GNN 에서 가장 핵심원리이기에 매우 중요합니다.

Aggregation 과정을 더 자세하게 수학적으로 알아보면 다음과 같습니다. 

 

 

 

The Simplest GNN