GNN(Graph Neural Network)

[참고 논문]

SCARSELLI, Franco, et al. The graph neural network model. IEEE transactions on neural networks, 2008, 20.1: 61-80.

https://ro.uow.edu.au/cgi/viewcontent.cgi?article=10501&context=infopapers 

 

1. 그래프(Graph)

 노드(node)와 간선(edge)로 이루어진 데이터 구조

 노드 간 상호 관계 등을 분석할 때 쓰임

 소셜 네트워크, 유튜브(SNS 등) 알고리즘 추천, 바이러스 확산 추론 등에 활용

•  그래프는 G=(V,E)로 정의
•   V : 점(node)들의 집합
•   E : 점을 잇는 간선(edge)들의 집합
• 그래프는 Adjaceny Matrix(인접행렬)로 표현 - 점의 개수에 따라 (n x n)로 표현

복잡한 문제를 더 간단한 표현으로 단순화 할 수 있고 다른 관점으로 표현 가능

1) 그래프는 좋은 데이터이지만 직관적으로 분석하는데 어려움이 있음

• 그래프는 유클리드 공간 X
• 고정된 형태가 아님(=노드들의 연결 관계가 같은 두 개의 그래프는 다른 형태로 존재할 수 있음)
• 직관적으로 해석 및 시각화가 어려움

2) 기존 그래프 분석 방법

• BFS, DFS 등 검색 알고리즘
• 최단 경로 알고리즘
• 신장 트리 알고리즘
• 클러스터링 방법

 

2. GNN(Graph Neural Network)

 Image, Sequential data 등의 input data 구조가 그래프일 때 그래프 데이터를 학습

1) GNN을 통한 활용

• Node Classification - node embedding을 통해 각 점(node)들의 특성을 분류
  • 유튜브 영상 분류 등
• Link Prediction - 점들의 상호 관계를 추론하고 해당 연관성을 파악
  • SNS 친구추천 등
• Graph Classification - 그래프 전체를 분류
  • 분자구조 데이터 분석 등

2) Node embedding

• GNN으로 학습하고 마지막 업데이트 시, 그 상태를 Node embedding

 

이외에도 GNN에서 CNN을 결합한 GCN 등의 많은 기법들이 있음