Massage passing

1. GNN

GNN은 그래프 구조의 데이터를 처리하기 위한 딥러닝 모델이다. 그래프의 노드, 엣지, 속성을 입력으로 받아 노드 혹은 특징 벡터를 학습한다. 기본적으로 메시지 패싱 기법을 사용하여 노드의 정보를 받아 특징 벡터를 업데이트하며 일반적으로 손실 함수를 정의하고 역전파를 통해 학습된다.

 

2. 그래프 데이터

노드와 엣지[노드 간 관계 혹은 상호작용]로 이루어 자료 구조이다. 이 구조는 네트워크 형태의 관계나 연결성을 설명하는데 사용된다. 

 

 

1) 그래프 예시

1. 추천 시스템의 경우

노드 : 유저 / 아이템

엣지 : 유저와 아이템의 관계 [조회 / 클릭 / 구매 등]

 

2. sns의 경우

노드 : 유저

엣지 : 유저의 관계 [팔로우 등]

 

3. 생물의 경우

노드 : 단백질, 유전자 등의 분자

엣지 : 단백질 간의 상호작용, 유전자 간의 관계

 

2) 그래프 종류

1. Directed Graph [방향 그래프]

    - 엣지에 방향이 있어 한 쪽 방향으로만 연결된다.

 

2. Undirected Graph [무방향 그래프]

    - 엣지에 방향이 없어서 두 노드 간 관계가 대칭적이다.

 

3. Weighted Graph [가중 그래프]

    - 엣지에 가중치가 있어 관계의 강도나 비용을 나타낸다.

 

4. Attribute Graph [속성 그래프]

    - 노드나 엣지가 속성을 가지고 있다.

 

5. Complete Graph [완전 그래프]

    - 한 노드에서 다른 노드와 연결되어 최대 엣지 수를 갖는다.

 

3. 메시지 패싱 [Message Passing]

메시지 패싱의 원리는 메시지 -> 집계 -> 업데이트 순서로 이루어진다.

 

1) 메시지 생성

$m_{u \rightarrow v} = f(h_{u}, h_{v}, e_{u, v})$

 

$u , v$ 는 노드를 뜻하며, $m_{u \rightarrow v}$ 는 $u$ 에서 $v$ 에 전송하는 것을 뜻한다.

$h_{u}$ 와 $h_{v}$ 는 각 노드의 임베딩 벡터, $e_{u, v}$ 는 노드를 연결하는 엣지의 특징을 뜻한다.

 

2) 집계

$M_{v} = AGG(\{ m_{u \rightarrow v} | u \in \mathcal{N}(v) \})$

 

$M_{v}$ 는 노드 $v$ 가 이웃 노드들로부터 집계한 메시지를 뜻하며,

$\mathcal{N}(v)$ 는 노드 $v$ 의 이웃 집합을 뜻한다.

 

3) 업데이트

$h'_{v} = \sigma(W \cdot [h_{v}, M_{v}])$

 

$h'_{v}$ 는 업데이트된 노드 $v$ 의 임베딩을 뜻하고, $W$ 는 가중치 행렬을 뜻한다.

$[h_{v} , M_{v}]$ 는 노드 $v$ 의 기존 임베딩과 집계된 메시지를 결합한 벡터를 뜻한다.

 

import torch
import torch.nn as nn
import torch.nn.functional as F


def forward(x, adjacency_matrix, num_node_features, hidden_channels, num_of_class):

    # 첫 번째 레이어: 인접 행렬과 특징 행렬의 곱 -> 선형 변환 -> 활성화 함수 적용
    x = torch.mm(adjacency_matrix, x)  # 인접 행렬과 특징 행렬 곱셈
    linear1 = nn.Linear(num_node_features, hidden_channels)
    x = linear1(x)
    x = F.relu(x)

    # 두 번째 레이어: 인접 행렬과 새로운 특징 행렬의 곱 -> 선형 변환
    x = torch.mm(adjacency_matrix, x)
    linear2 = nn.Linear(hidden_channels, num_of_class)
    x = linear2(x)
    
    return x