Graph 유형 정리 (GNN)

그래프를 구성하는 가장 큰 요소는 노드와 엣지이다.

즉, 연결을 하고자하는 대상과 연결고리를 어떻게 표현할지에 대한 연구라고 생각하면 된다.

 

Graph Types

1. Directed Graph
- 두 노드 사이의 방향이 존재하는 그래프로 사람의 움직임

- 예를 들면 서울에서 부산으로 이동을 나타낸다던지, 은행에서 입금과 출금자간 재화의 흐름을 보여주는 등 각 노드간의 연결 관계를 나타낼 수 있음

2. Homogeneous / Heterogeneous Graph
- Homogeneous : 동질의 / Heterogeneous : 이질의 라는 뜻에서 graph 유형을 추정해보면

- Homogeneous 그래프는 모든 노드가 같은 성질을 갖고 있는 형태로, 노드의 종류가 같은 것을 의미한다. 인물 관계를 나타낸다면 모든 노드는 사람을 의미하는 homogeneity를 갖는 노드로 구성. 
- Heterogeneous 그래프는 노드가 여러 종류의 성질을 가지는 형태로 유저-구매상품, 저자-논문페이퍼 등 여러 형태들을 각각의 노드로 표현하는 형태를 말함 --> 즉 노드는 이질적인 형태(heterogeneity)를 갖는다.

Homogeneous Graphs	Heterogeneous Graphs
각 노드는 한개 유형의 정보만 담고 있다	각 노드들은 다양한 형태의 정보를 담고 있다
엣지로 연결된 관계는 하나의 유형이다	엣지는 연결한 노드 형태에 따라 다양한 유형을 가질 수 있다
노드간의 유사성을 정의하기가 비교적 쉽다	각 노드 페어간 유사성을 정의하기 어렵다
NN을 구성하기에 비교적 용이함(embedding 측면)	NN을 구성하는데 어려움. 극히 소수의 GNN형태만 가능할 것

3. Edge-informative Graph
- 그래프를 구성하는 edge가 가중치를 가지거나 여러 종류의 성질을 갖는 그래프

- 이런 경우에는 기존의 edge를 node로 변환하여 기존 노드 voriginal​와 edge 노드 vedge​로 나뉘는 bipartite graph를 만들어 그래프를 재구성하여 풀 수 있음

- 이 경우에도 임의의 두 노드 사이의 edge는 여러개가 될 수 있음

4. Dynamic Graph
- 그래프의 구조가 달라지는 케이스

- node의 수가 달라질수 도 있으며, 시간의 변화에 따라 edge의 연결 상태도 달라질 수 있음Dynamic graph는 그래프의 구조는 같지만 각 node의 feature와 edge feature의 정보가 시시각각 변화하며 들어오는 경우를 말한다.

- 특히 시계열 데이터를 이용한 그래프 구조의 경우, 시계열에 따라 달라질 수 있음

 

참조

https://velog.io/@thecho7/Graph-Neural-Network-3

https://slidetodoc.com/neural-networks-for-processing-heterogeneous-graphs-federica-baccini/

https://www.researchgate.net/figure/Different-representations-of-a-dynamic-graph-A-Modeling-a-discrete-time-dynamic-graph_fig5_347300725