[개념정리] 그래프 신경망(Graph Neural Network / GNN) (2)

[본 포스팅은 다음 포스팅의 내용을 참조하여 작성하였습니다. https://viso.ai/deep-learning/graph-neural-networks/]

Graph Neural Networks (GNNs) - 2024 Comprehensive Guide - viso.ai

 

 

GNN에 대한 개략적인 개념과 이해는 이전 포스팅을 참조해주시면 되겠습니다.

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (1)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (1)

 

 

1. GNN 개념

1) GNN이 수행하는 예측 작업

- GNN의 주요 목표는 그래프 구조의 표현(임베딩)을 학습하는 것입니다.

- GNN은 노드의 속성과 그래프의 위상구조를 모두 포착할 수 있으며, 이러한 표현들은 노드 분류(노드의 레이블 결정), 링크 예측( 두 노드 간의 엣지 존재 예측), 그래프 분류(전체 그래프 분류)와 같은 다양한 작업에 활용할 수 있습니다.

- 즉, GNN은 Node-level Prediction / Edge-level Predcition / Graph-level Prediction 을 수행한다고 보시면 되겠습니다. 

 * Node-level Prediction : 노드가 무엇인지 해당 범주를 예측

 * Edge-level Prediction : 두 노드간의 연결 가능성을 예측

 * Graph-level Prediction : 구조와 노드 속성에 기반해 전체 그래프의 형태를 예측

 

2) 그래프에 대한 기본 개념

- Verticles(Nodes)와 Edges

 * Verticle 또는 Node는 한 점을 뜻하며, Edge는 이들을 연결한 선을 의미합니다. 이것들의 집합이 바로 Graph라고 정의됩니다.

 

- Directed Graph 와 Undirected Graph

* 방향성이 정해져있는 것은 Directed, 그렇지 않으면 Undireced Graph라고 한다. 

Directed Graph

Undirected Graph

 

이때, 엣지가 weight를 가지고 있다면, Weighted Grpah라고 한다

 

3) Graph Representation 이란?

- Graph Representation, 즉 그래프 표현이란 그래프의 구조와 특징을 신경망에서 처리할 수 있도록 인코딩 하는 방법을 말합니다. 

- 그래프는 노드의 데이터뿐만 아니라 데이터 포인트 간의 관계를 포함하는 것으로, 이러한 노드 간의 연결을 나타내기 위해 Graph Representation이 필요하게 됩니다.

 

- Adjacency Matrix(인접행렬)

 * Adjacency Matrix는 각 노드에 연결된 모든 다른 노드를 나열하는 행렬을 의미합니다.

 * 예를 들어, 아래 예시에서는 노드 A에는 노드 B와 C가 연결되어 있으므로, 배열에서 해당하는 값이 1이 되고, 그렇지 않은 경우에는 0으로 표시합니다.

 

 

- Incidence Matrix(발생 행렬)

 * Incidence Matrix는 N x M 크기의 행렬로, 여기서 N은 노드의 수, M은 그래프의 엣지 수를 나타냅니다. 간단히 말해, 그래프를 행렬 형태로 표현하는데 사용됩니다. 특정 노드가 특정 엣지를 가지면 행렬 값이 1이되고, 가지지 않으면 0이 되게 합니다.

 * 아래 예시를 본다면, 노드 A가 엣지 E1과 연결되어 있으면 Incidence Matrix에서 해당 값은 1로 표시되고, 노드 A가 엣지 E4와 연결되어 있지 않으면 해당 위치에는 0으로 표시됩니다.

 

- Degree Matrix(차수 행렬)

 * 차수 행렬은 각 노드에 연결된 엣지의 수를 포함하는 대각 행렬을 말합니다.

 * 이 행렬의 대각선 요소들은 각 노드의 차수(Degree)를 나타내며, 대각선 이외의 요소들은 0이 됩니다.

 * 아래 예시를 보면, 노드 A에 3개의 엣지가 연결되어 있다면, 차수 행렬에서 A에 해당하는 대각선 요소는 3이 됩니다. 이와 같이, 각 노드의 차수를 대각선에 배치하여 그래프의 연결 정도를 표현합니다.

 

- 위 3가지의 표현에 대해서 요약해보면 아래와 같습니다.

 a) Adjacency Matrix

 * 구성 : NxN 크기의 행렬로, 노드 간의 직접 연결 여부를 0과 1로 표시

 * 유용성 : 경로 존재 확인, 네트워크 구조 분석

b) Incidence Matrix

 * 구성 : N x M 크기의 행렬로, 노드와 엣지 간의 연결 여부를 0과 1로 표시

 * 유용성 : 엣지 중심 분석, 그래프 구조 변화 분석

c) Degree Matrix

 * 구성 : N x N 크기의 대각행렬로, 각 노드의 차수를 대각선에 표시

 * 유용성 : 노드의 중요도 분석, 그래프 라플라시안 계산