GNN [Graph Neural Network] - 1

1. 그래프 모델이 나온 이유?

CNN, RNN, Transformer 등의 Representation Learning 모델은 복잡한 구조와 관계를 지니는 경우 임베딩에 한계가 있었고, 이를 해결하기 위해 그래프를 사용한 신경망 모델이 제안되었다. 그래프 모델은 관계와 상호작용을 다루기에 적합하고 더 간단하게 표현 할 수 있다.

 

• CNN : Euclidean 공간에서 행과 열로 배열된 픽셀들로 이루어진 이미지에서 특징을 추출함
• RNN : Recurrent 구조를 통해 input으로 주어지는 시계열 데이터인 sequence의 특징을 추출함
• Transformer : self-attention 구조를 통해 어떤 한 부분에서 주의를 기울여야 할 여러 부분을 병렬적으로 함께 처리함으로써 input의 특징을 추출함

 

2. 그래프?

그래프는 노드(점)와 노드를 연결하는 엣지(선)의 집합인 데이터 구조이며,  $G=(V,E)$ 로 정의할 수 있다. 관계나 상호작용이 있는 데이터 분석시 주로 사용된다. 방향이 있는 방향 그래프 혹은 방향이 없는 무방향 그래프로 나눠지며, 모든 노드와 엣지가 동일한 동질이거나 노드 또는 엣지가 다른 이질일 수 있다. 하이퍼그래프는 하나의 엣지가 두 개 이상의 노드를 연결할 수 있는 그래프 유형이다.

 

출처 : https://jypark1111.tistory.com/100

 

그래프의 유형을 좀 더 정리하자면, 두 노드 사이에 최대 한 개의 엣지가 있는 그래프를 simple graph, 두개 이상의 엣지가 있는 그래프를 multi graph 라고 한다. 또 모든 노드가 두개의 그룹 중 한 그룹에 속하고, 서로 다른 그룹에 속하는 노드끼리만 엣지가 존재하는 그래프를 이분 그래프라고 하며, 이 경우 이분 매칭으로 풀어야 하는 알고리즘에서 자주 사용된다.

 

어떤 노드가 루트 노드인지 지정되지 않는 경우 루트 없는 트리라고 하며, 사이클 [엣지를 한 번만 거쳐서 자기 자신으로 돌아오는 path가 존재] 이 없는 그래프를 DAG[Direcrted Actclic Graph] 라고 한다.

 

그래프의 장점은 다음과 같다.

• 관계나 상호작용 반영이 가능하다.
• 복잡한 문제를 단순화 할 수도 있고, 기존의 신경망과는 다른 관점으로 표현할 수 있다.

 

3. 기존 그래프 분석 방법

기존의 그래프 분석 방법은 알고리즘 기반 방법이다.

• 검색 알고리즘 [BFS, DFS 등]
• 최단 경로 알고리즘 [Dijkstra 알고리즘, A* 알고리즘 등]
• 신장 트리 알고리즘 [Prim 알고리즘, Kruskal 알고리즘 등]
• 클러스터링 방법 [연결 성분, 클러스터링 계수 등]

위의 알고리즘 한계는 알고리즘 적용 전 input 그래프의 사전 지식이 필요하다는 점이다.

 

4. GNN?

Graph Neural Network는 input과 output이 모두 그래프인 모델을 뜻한다. GNN의 목적은 그래프의 노드들을 임베딩 하는 것으로, 노드를 임베딩할 때 그래프의 구조를 반영하여 임베딩 한다. 그래프의 구조 [= 이웃 노드들의 정보] 를 반영하는 것을 메시지 패싱(Message Passing) 이라고 한다.

 

다음과 같은 문제에 주로 사용이 된다.

• Node Classification : 노드 임베딩을 통해 노드를 분류하는 문제
• Link Prediction : 노드 사이의 관계를 파악하고 연관성을 예측하는 문제
• Graph Classification : 그래프의 클래스를 예측하는 문제

 

 

5. 참고

• https://jypark1111.tistory.com/100
• https://glanceyes.com/entry/%EC%B6%94%EC%B2%9C-%EC%8B%9C%EC%8A%A4%ED%85%9C-GNNGraph-Neural-Network%EC%99%80-%EC%9D%B4%EB%A5%BC-%EC%9D%91%EC%9A%A9%ED%95%9C-NGCFNeural-Graph-Collaborative-Filtering%EC%99%80-LightGCN
• https://medium.com/watcha/gnn-%EC%86%8C%EA%B0%9C-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EB%85%BC%EB%AC%B8%EA%B9%8C%EC%A7%80-96567b783479
• https://haandol.github.io/2023/12/19/graph-neural-network-for-software-developers.html

개발자를 위한 Graph Neural Network (GNN) (Graph Neural Network (GNN) for Software Developers), Haandol

 

GNN 소개 — 기초부터 논문까지

 

GNN(Graph Neural Network)

 

GNN(Graph Neural Network)의 정의와 특징 그리고 추천시스템에서의 GNN 계열 모델