GNN(Graph Neural Network)

2023.07.23 - [DeepLearning/Paper Riview] - GNN기반 추천 시스템 조사 - 논문 리뷰: Graph neural networks in recommender systems: a survey

GNN기반 추천 시스템 조사 - 논문 리뷰: Graph neural networks in recommender systems: a survey

GNN(Graph Neural Networks)

1. Graph

그래프는 점(노드)과 이를 연결하는 선(엣지)의 집합이다. 노드의 이웃은 노드에 연결된 노드의 집합이다. 그래프는 방향이 있는 방향 그래프거나 방향이 없는 무방향 그래프가 존재하며, 또한 동질(모든 노드와 엣지가 동일)이거나 이질(노드 또는 엣지가 다름)일 수도 있다. 하이퍼그래프는 하나의 엣지가 두 개이상의 노드를 연결할 수 있는 그래프 유형이다.

Grpah = G(V,E)

2. GNN

GNN은 Graph Neural Network의 약자로, 그래프 데이터 분석에서 사용하는 딥러닝 모델이다. 예를 들어, 소셜 네트워크는 친구 관계를 그래프로 표현할 수 있다.

GNN은 이러한 그래프 데이터를 입력으로 받아서, 각 노드의 임베딩을 추출하거나, 그래프 전체를 분류하는 등의 작업을 수행한다. GNN은 일반적으로 메시지 전달 방식을 사용하여, 각 노드의 임베딩을 계산합니다. 이때, 각 노드의 이웃 노드와의 관계를 이용하여, 해당 노드의 임베딩을 갱신한다.

GNN은 반복적인 프로세스를 사용하여 인접 노드의 특징 정보를 집계하고 이를 현재 중앙 노드 표현과 통합한다. 이는 집계 및 업데이트 작업을 모두 포함하는 여러 레이어를 쌓아 수행된다. 그 결과 제공된 그래프 데이터를 기반으로 보다 정확한 예측이 가능하다.

집계 단계에서는 평균 풀링 또는 어텐션 메커니즘을 사용하여 인접 노드의 특징을 결합한다. 업데이트 단계에서는 GRU라는 연결 또는 합계 연산과 같은 다양한 전략을 사용하여 집계된 피처를 중앙 노드 특징과 통합한다.

그래프에서 중앙노드란, 그래프 구조에서 중심에 위치한 노드를 의미한다. 예를 들어, 소셜 네트워크에서 친구 관계를 그래프로 표현했을 때, 친구들 사이에서 가장 많은 연결을 가지고 있는 노드를 중앙노드라고 부를 수 있다.

• GNN Task
  • Node : 특정 노드가 어떤 레이블에 속하는지
  • Edge : 연결되지 않은 두 정점이 연결가능성이 있는지
  • Graph : 그래프 자체가 어떤 레이블에 속하는지

  ---

• GNN의 구성 요소
• GNN에서 그래프를 구성하기 위해서는 3가지가 필요하다.

1. Vertex(node)
2. Edge
3. Feature

—# Vertext와 Edge와의 관계를 adjacency matrix(인접행렬)로 나타냄

—# Feature는 Feature metrix(특징 행렬)로 나타냄

Graph represctation learning이 먼저 시작하고 딥러닝을 접목시킨 것이 GNN이다.

추천 시스템에 사용되는 그래프 신경망(GNN)기법은 5가지가 존재한다.

• 1. GCN(Graph Convolutional Network)
• 2. GraphSAGE(Graph SAmple and aggreGatE)
• 3. GAT(Graph Attention Network)
• 4. GGNN(Graph Gated Neural Network)
• 5. HGNN(Hypergraph Neural Network)

3. 노드 임베딩

GNN은 여러 노드들의 고차원 정보를 저차원 공간으로 임베딩하여 그 특성을 파악한다.

그래프 데이터 분석에서 노드 임베딩은 각 노드를 벡터 형태로 변환하는 것을 의미한다. 이를 통해 노드 간의 유사도를 계산하거나, 머신러닝 모델의 입력으로 활용할 수 있다.

예를 들어, 소셜 네트워크 그래프에서 각 노드는 사용자를 나타내고, 각 노드의 임베딩은 해당 사용자의 특성을 나타내는 벡터로 변환다. 이렇게 변환된 벡터를 이용해 사용자 간의 유사도를 계산하거나, 머신러닝 모델의 입력으로 활용할 수 있다. 또한, 임베딩은 다른 그래프 데이터 분석 알고리즘과 결합하여 그래프의 정보를 보다 효과적으로 활용할 수 있도록 한다.

3-1. 임베딩 종류

1. 그래프 스펙트럴 방법: 그래프 스펙트럴 방법은 노드 임베딩을 특잇값 분해(SVD)나 라플라스 행렬(Laplacian matrix) 등의 그래프 스펙트럴 분석을 통해 추출 이 방법은 그래프 전체의 정보를 이용해 노드 임베딩을 학습하며, 그래프의 대칭성과 성질을 이용해 임베딩을 생성한다. 대표적으로 DeepWalk, node2vec, LINE, SDNE 등이 있다.
2. 그래프 신경망 방법: 그래프 신경망 방법은 메시지 패싱(Message Passing)을 이용해 노드의 임베딩을 학습한다. 메시지 패싱은 이웃 노드들과의 정보교환을 통해 노드의 임베딩을 계산한다. 이 방법은 노드간의 구조적인 관계와 특성을 잘 반영할 수 있으며, 그래프의 구조와 노드의 특성을 모두 고려할 수 있다. 대표적으로 GCN, GAT, GraphSAGE, Graph Convolutional Matrix Completion (GCMC) 등이 있습니다.

• Neighborhood-based Methods
• 노드의 임베딩을 학습하기 위해 노드의 이웃 노드들의 특징을 이용하는 방법. 이웃 노드들의 특징을 평균 내거나, 가중 평균을 취하는 등의 방법으로 노드의 임베딩을 계산한다. 예를 들어, GCN(Graph Convolutional Network)은 이웃 노드들의 특징과 가중치를 합해서 노드의 임베딩을 계산한다.
• Random Walk-based Methods
• 노드의 임베딩을 학습하기 위해 무작위로 그래프를 탐색하는 방법입니다. 무작위로 그래프를 탐색하면서 노드의 이웃 노드들과의 유사도를 계산하고, 이를 이용해 노드의 임베딩을 학습합니다. 예를 들어, DeepWalk는 무작위로 그래프를 탐색하면서 각 노드와 인접한 노드들의 시퀀스를 생성하고, 이를 이용해 Word2Vec과 유사한 방법으로 노드의 임베딩을 학습합니다.
• Spectral-based Methods
• 노드의 임베딩을 학습하기 위해 그래프의 라플라시안 행렬을 이용하는 방법입니다. 그래프의 라플라시안 행렬을 이용하면 그래프의 고유벡터를 계산할 수 있으며, 이를 이용해 노드의 임베딩을 계산합니다. 예를 들어, GraphSAGE는 그래프의 라플라시안 행렬을 이용해 노드의 임베딩을 계산합니다.
• Attention-based Methods
• 노드의 임베딩을 학습하기 위해 노드 간의 상호작용을 모델링하는 방법입니다. 이 방법은 노드 간의 유사도를 계산하고, 이를 이용해 노드의 임베딩을 계산합니다. 예를 들어, GAT(Graph Attention Network)은 이웃 노드들과의 상호작용을 계산하는데, 이를 위해 어텐션 메커니즘을 사용합니다

메시지 기반 노드 임베딩

• A 노드에 특징을 업데이트 하기 위해서 자신과 연결된 이웃 노드들의 특징을 집계하여 자신의 특징을 업데이트 하는 방식으로 1번 연결된 이웃에 대한 특징만을 집계하는것으로 인공지능 One-layer와 유사하다.

• 위와 같은 방식에서 A와 이웃된 노드의 또 다른 이웃들의 정보를 기준으로 레이어를 증가시킬 수 있다.

https://github.com/pyg-team/pytorch_geometric

데이터 셋

1. Cora: 컴퓨터 과학 논문 데이터셋으로, 논문을 노드로, 각 논문의 키워드를 feature로 갖고 있다.
2. Citeseer: Cora와 비슷한 데이터셋으로, 컴퓨터 과학 분야의 논문을 노드로, 논문의 키워드를 feature로 갖고 있다.
3. Pubmed: 의학 분야의 논문 데이터셋으로, 논문을 노드로, 논문의 키워드를 feature로 갖고 있다.
4. Reddit: 소셜 미디어 사이트인 Reddit의 서브레딧 데이터셋으로, 각 포스트를 노드로, 사용자가 작성한 텍스트를 feature로 갖고 있다.
5. PPI (Protein-Protein Interaction): 단백질 상호작용 데이터셋으로, 각 단백질을 노드로, 단백질의 특징을 feature로 갖고 있다.

PyTorch Geometric에서는 TUDataset, Planetoid, Coauthor 등 다양한 데이터셋을 제공하고 있고, DGL에서도 Reddit, Amazon 등 대표적인 GNN 데이터셋을 제공한다.

라이브러리

Python에서 GNN 모델 설계를 지원하는 다양한 라이브러리들이 존재한다.

1. PyTorch Geometric: PyTorch Geometric는 PyTorch 기반의 GNN 라이브러리로 대규모 그래프에서 GNN을 학습시키기 위한 다양한 유틸리티 함수와 함께 다양한 GNN 모델을 구현할 수 있다.
2. Deep Graph Library (DGL): DGL은 MXNet, PyTorch 및 TensorFlow에서 GNN 모델을 구현하고 학습시키기 위한 라이브러리. 여러 가지 그래프 레이아웃과 함께 다양한 GNN 모델과 레이어를 구현할 수 있다.
3. Spektral: Spektral은 Keras 기반의 GNN 라이브러리로 다양한 GNN 모델을 쉽게 구현하고 학습시킬 수 있다.
4. NetworkX: NetworkX는 Python에서 네트워크 분석을 위한 라이브러리입니다. NetworkX를 사용하여 GNN 모델을 구현하고 학습시킬 수 있다.