GNN과 Graph 자료구조의 특성

1. Graph 자료 구조

Vertice와 edge들을 가지고 구성되어있는 자료구조이다. edge들은 vertices 간의 연결된것을 의미힌다.

 

 

2. 그래프 자료구조를 처리하기 어려운 이유

• Graph Data는 복잡하다. : 전통적인 ML, DL 도구들은 simple data types에 특화되어 있다.
        ex) 이미지 데이터는 같은 구조와 사이즈여서 fixed-size grid graph로 생각할 수 있음 , 순차적인 text or speech 데이터
• 그래프는 유클리드 공간에 있지 않다. 즉, 좌표계로 표현할 수 없다. 시계열 데이터, 음성, 이미지 데이터가 2차원 및 3차원 유클리드 공간에 매핑을 할 수 있는 것과 달리 그래프 데이터는 매핑하기 어렵다.
• 그래프는 고정된 형태가 아니다. : 가변적인 크기의 정렬되지 않은 node들로 이루어져 있다. Graph 데이터의 이웃 노드들 크기가 각각 다르다. 순서가 없기 때문에, 데이터의 시작점과 끝점이 없다.
• DL 툴들은 간단한 순서나 형식에 특정되어 있다.
• 전통적인 ML 알고리즘은 각각을 독립적인 인스턴스로 보고 있다. 하지만 실제 그래프 데이터는 다양한 타입들의 link에 의해 표현되는 다른 이웃 노드들과의 연관성을 가지고 있다.
  
  
• 인접 그래프 구조에서, n개의 nodes 가 있다면, 그 인접그래프는 (n*n) 크기이다.
• node 가 f 개의 features를 가지고 있다면, node feature matrix X는 (n*f) 크기이다.

 

3. 그럼에도 그래프 자료구조가 필요한 이유 

• 노드와 노드간의 ‘관계’, ‘상호 작용’ 같은 추상적 개념을 다룰 수 있다.
• SNS, 바이러스 확산 등을 표현하기 적합하다.

4. GNN 의 개념

• Graph Neural Network : 그래프 구조에 기반하여 작동하는 뉴럴 네트워크 
• node와 그 node로 부터 생성되는 numeric 한 값의 관계를 모델링할 수 있다. 
• node-level, edge-level, graph-level에서 예측한다.
• 각 노드는 인접 노드의 feature vector를 집계하여 새로운 feature vector를 계산한다.

5. Recurrent GNN

• GNN은 주로 연결관계와 이웃 node들의 상태를 이용하여, 각 node들의 상태를 업데이트하고, 마지막 상태들을 통해 예측한다. 마지막 상태는 node embedding이라고 한다.
• Graph node는 recurrent unit이고, node에 있는 information은 embedding에 해당되는데, unit들이 모두 반복되어서, node가 가진 information이 손실되지 않는다.

6. GNN 의 표기 

hv (k) 는 k 번째 반복 혹은 k번째 layer에서 node v의 feature vector이다. 
N (v) 는 node v에서 인접한 node들의 집합이다. 

GNN은 이웃 노드들을 aggregation 하는 작업을 반복적으로 수행하여 상태를 업데이트한다. 

7. Node Embedding 
node 를 vector 형태로 표현하는 것이다. 
이 embedding 방식에는 두가지가 있다. 

1) Transductive method (변환식 방법)
     ex) Node2Vec, Deepwalk 


2) Inductive method (귀납식 방법)
     ex) GNN

 

참고 유투브 영상 :

https://www.youtube.com/watch?v=cWIeTMklzNg