1. Graph란?
- 그래프(Graph)란, 꼭지점(node)들과 그 노드를 잇는 선(간선, edge)들을 사용하여 데이터를 표현하는 자료구조이다.
- edge에 따라 다음과 같은 종류로 나뉘어진다.
- 방향 유무
- directed / undirected
- 가중치 유무
- weighted / unweighted
- 방향 유무
[ Graph를 사용하는 이유 ]
- 관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다.
- 복잡한 문제를 더 간단한 표현으로 단순화할 수 있다.
- 소셜 네트워크, 바이러스 확산, 유저-아이템 상호작용 등을 모델링할 수 있다.
- Non-Euclidean Space의 표현 및 학습이 가능하다.
- 흔히 다루는 이미지, 텍스트, 정형데이터는 격자 형태의 데이터로 표현 가능하다.
- SNS 데이터, 분자(molecule) 데이터 등은 격자 형태로 표현하기 부적절하므로, Non-Euclidean Space에 표현해야 한다.
2. Graph의 표현
2-1. Adjacency Matrix
1) Undirected
Undirected의 경우, edge의 방향성이 정해지지 않은 그래프를 표현한 행렬이다.
즉, 행렬로 표현했을 때 그림 우측의 행렬과 같이 edge로 연결된 모든 node에 대해서 연결되기만 하면 1로 표현되므로, Symmetric한 행렬로 구성된다.
2) Directed
Directed의 경우, edge의 방향성이 존재하는 그래프를 표현한 행렬이다.
행렬의 행이 입력, 열이 출력으로 보았을때 화살표를 받는 쪽이 1로 표현된다. 예를 들어 1 -> 2 인경우, $a_{12}=1$로 표현된다. 그러므로 그림의 우측의 행렬과 같이 Symmetric하지 않다.
3) Directed + Self-Loop
방향성이 있는 인접행렬과 Self-Loop를 더한 형태이다. Self-Loop는 자기자신과의 연결성을 1로 표현하는 것이며, 이는 항등행렬($I$)를 더하는 것과 같으므로, 인접행렬(Adjacency matrix) + 항등행렬(Identity matrix : Self-Loop)로 표현된다.
4) Weighted Directed
Weighted의 경우, 연결성을 표현하는 인접행렬의 성분값에 가중치를 두는 것이다.
앞서 언급한 다른 인접행렬의 경우는 단순히 연결성(1,0)을 표현하는데 그쳤지만, Weighted Directed는 가중치로 설정한다. 성분이 0이 아니면 연결이 된 것이며, 그 값만큼 가중치를 가지는 것이다.
이때, 그 값을 Edge Information이라고도 한다.
2-2. Degree Matrix
Degree Matrix는 각 노드가 주변 n개의 노드와 연결되어 있는지를 표현한 행렬이다. 위의 오른쪽 행렬과 수식처럼 표현되며, $a_{11}$의 성분은 1 node와 연결된 node의 수가 2(연결된 edge의 수가 2)인 것이다.
2-3. Laplacian Matrix
Laplacian Matrix는 Degree Matrix에서 인접행렬을 뺀 행렬이다.
위 그림의 오른쪽 행렬처럼 대각성분과 성분이 0인 부분을 제외한 나머지 성분은 -1로 표현된다.
2-1. Node-Feature Matrix
Node-Feature Matrix는 각 노드의 Hidden Representation를 모아놓은 행렬이다.
이때, Hidden Representation은 주로 Embedding Vector 등이 된다.
3. GNN
3-1. GNN이란?
GNN(Graph Neural Networks)는 그래프로 표현할 수 있는 데이터를 처리하기 위한 인공신경망을 말한다.
그래프를 구성할 때 각 node를 잘 표현하는 임베딩이 필요하다. 즉, 이웃노드들 간의 연결성, 가중치 등의 정보를 이용해서 특정 node를 표현할 수 있는 특징 벡터를 찾아내는 것이 목표가 된다.
"특징 벡터를 찾는다."는 것은 CNN, LSTM 등 다른 모델들에서도 공통적으로 확인할 수 있는 개념이다.
- CNN은 이미지(픽셀 데이터)에서 특징을 추출하여 벡터를 만들고, 이를 통해 목적에 맞는 연산을 수행한다.
- LSTM은 시계열 데이터에서 특징을 추출하여 벡터를 만들고, 이를 통해 목적에 맞는 연산을 수행한다.
- GNN 역시, 그래프 데이터에서 특징을 추출하고 이를 통해 목적에 맞는 연산을 수행한다.
즉, 그래프로 표현될 수 있는 데이터에서 특징을 추출하고 목적에 맞는 task( 분류 등 )을 수행하는 모델 구조가 GNN이다.
위의 그림은 GNN을 사용해 node $u$를 잘 표현하는 $d$ 차원의 벡터를 만든다는 것을 간단하게 보여준다.
이러한 과정에는 node와 edge의 정보와 관계를 표현할 수 있는 수단이 필요하며, 대부분의 경우 앞에서 언급한 Node-Feature Matrix와 인접행렬(Adjacency Matrix)를 사용하여 표현한다.
3-2. GNN의 학습과정
학습과정은 다른 NN 구조와 크게 다르지 않다.
우선, 원래의 데이터 구조를 그래프로 표현하는 것이 필요하다. node와 edge의 정보, 관계등을 표현하기 위해서이다. 그런 다음, GNN을 거쳐 특징 벡터를 구성하고 이를 통해 prediction과 label의 차이를 통해 학습하게 된다.
3-3. GNN의 Task
GNN을 사용한 Task의 종류에는 크게 세 가지가 있다.
우선, 주어진 데이터를 학습한 GNN을 통해 추출한 각 node $i$의 특징 벡터를 $z_{i}$라고 한다.
3-3-1. Node Classification
Node Classification은 특징 벡터 $z_i$를 통해 node $i$를 원하는 label로 분류하는 task이다. 즉, 임의의 한 node가 어떤 label에 속하는지를 분류하는 것이다.
$$\textrm{softmax}(z_i)$$
3-3-2. Graph Classification
Graph Classification은 그래프를 구성하는 전체 node에 대한 특징 벡터 $z_i$를 모두 더한 것을 그래프 자체에 대한 표현으로 삼고, 해당 그래프가 어떤 label에 속하는지 분류하는 Task이다.
$$\textrm{softmax}(\sum_{i}^{}z_i)$$
3-3-3. Link Classification
Link Classification은 edge로 연결되지 않은 두 node $i$와 $j$가 서로 연결될 수 있는지를 예측하기 한 Task이다.
이는 두 node의 특징벡터를 내적함으로써 그 결과값이 클수록 서로 상호작용할 확률이 높은 것으로 예측하는 단계를 거친다.
$$ p(A_{ij})=\sigma (z_i^{T}z_j)$$
즉, GNN이 수행하는 Task는 주로 Classification이 되며, Node, Graph, Link를 Classification하는 것이 기본 목적이 되겠다.
4. GNN의 방법론
GNN의 방법론에는 크게 두 가지가 존재한다.
- Spectral 방법론
- Spatial 방법론
발전과정을 보면 Spatial한 Original GNN이 2005년 발표되었지만, 근 10년간 추가 연구가 없었다. 2015년에 Spectral 방법론을 사용한 연구가 등장한 후, GNN에 대한 추가 연구가 진행되었으며, GCN이 등장한 후 대부분의 연구는 Spatial 방법론으로 굳혀졌다.
그래서 우선 Spectral 방법론에 대해서 정리하고 Spatial 방법론으로 확장하겠다.
4-1. Spectral 방법론
Spectral 방법론은 말그대로 스펙트럼(Spectrum), 즉, 신호 전처리 분야에서 어떠한 신호를 스펙트럼처럼 분석하는 접근법이다.
스펙트럼처럼 분석하여 접근하는 다는 것은 다시 말해, 영상, 오디오, 이미지, 그래프 등을 단순한 요소의 합으로 분해하는 것을 의미한다. 이러한 분해의 대표적인 방법은 푸리에 변환(Fourier Transform)이 있는데, 이는 어떠한 신호를 sine과 cos sine 등 다양한 주파수를 갖는 주기함수들의 합으로 분해하는 것이다.
하지만,
GNN에서 Spectral은 그래프의 라플라시안 행렬(Laplacian Matrix)을 고윳값 분해(Eigen Decomposition)하는 것이다.
라플라시안 행렬 : Laplacian Matrix
라플라시안 행렬($L$)은 차수행렬($D$ : Degree Matrix)에서 인접행렬($A$ :Adjacency Matrix)를 뺀 것으로 정의된다.
편의를 위해 Undireced Graph로 생각하고 $L$이 symmetric하다고 가정한다.
각 node에 연결된 edge 수를 의미하는 차수 행렬에서 인접행렬을 뺀 라플라시안 행렬은 원래의 인접행렬을 변환한 것으로 이해할 수 있다. 이러한 라플라시안 행렬은 그래프의 유용한 특성을 찾고자 할 때 많이 사용한다.
고윳값과 고유벡터
https://kkuneeee.tistory.com/93
[Linear Algebra] Part17. 고윳값(Eigen Value)과 고유벡터(Eigen Vector)
선형대수에서 핵심이 되는 고윳값(Eigen Value)과 고유벡터(Eigen Vector)에 대해서 정리하고자 한다. 1. 정의 고윳값과 고유벡터의 정의는 다음 수식을 보면 알 수 있다. HTML 삽입 미리보기할 수 없는
kkuneeee.tistory.com
고윳값과 고유벡터에 대한 정리는 위의 포스팅을 참고한다.
그렇기에 따로 정리는 생략한다.
고윳값 분해
고윳값 분해는 행렬 $A$를 고윳값과 고유벡터로 분해하는 것을 의미한다.
고윳값 분해에 대한 자세한 정리는 추후 정리하는 포스팅을 참고하도록 하고 생략하도록 하겠다.
돌아와서, Spectral 방법론은 그래프의 라플라시안 행렬(Laplacian Matrix)을 고윳값 분해(Eigen Decomposition)한다고 했다.
고윳값 분해는 행렬을 구성하는 단위 직교 성분(Elementary Orthogonal Component)를 찾을 수 있는 방법이므로, 그래프 전반에서 핵심적인 정보를 뽑아내 보다 유의미한 정보를 추출하는 과정으로 생각할 수 있다.
조금 더 자세히 보자.
그래프의 라플라시안 행렬에서 고윳값 분해를 통해 찾은 고유벡터는 그래프의 topology 정보를 갖게 된다.
- 고윳값이 작은 고유벡터 : 그래프의 local 구조의 정보
- 고윳값이 큰 고유벡터 : 그래프의 global 구조의 정보
이러한 고유벡터에 대해 potential(signal, 어떤 한 node의 특징)이 주어지면, 고유벡터가 이루는 공간으로 투영하여 고유벡터들의 선형결합으로 표현할 수 있다. 이렇게 하면, 해당 signal이 어떻게 변화하는지(흩어지는지 : diffusion)에 대한 정보를 파악하는 것이 가능하다.
위의 히트맵은 어떤 그래프의 node(픽셀)에서 signal(특징)이 주어질때, 그 signal이 어떻게 흩어지는지 변화하는 것을 볼 수 있다.
Spectral 방법론은 그래프의 node간의 연결성 구조를 보존하면서 그래프의 topology(위상)을 파악하는 동시에 그래프에서 signal(특징)이 어떻게 다른 node로 퍼져나가는지를 이해하여 전반적으로 유의미한 특성을 찾아내고자 하는 것이며, 이를 그래프의 라플라시안 행렬의 고윳값 분해를 통해 수행한다.
고윳값 분해를 통해 찾아낸 고유벡터를 이용하여 Graph Fourier Transform을 정의한다.
Graph Fourier Transform은 라플라시안 행렬의 고유공간(고유벡터로 표현되는 공간)에 존재하는 임의의 행렬 $X$가 있을때, 이에 직교하는 공간 $L$의 orthonormal eigenvector space로 projection시켜서 그래프의 signal이 어떻게 흩어지는지를 얻는 것이다.
이 공간에서의 고유벡터는 그래프의 topology(위상) 정보를 가지며, 고유값에 따라 local 정보와 global 정보를 갖는 고유벡터가 존재한다. 또한 해당 공간에서 signal의 변화를 의미하는 벡터는 이러한 고유벡터들의 선형결합으로 표현될 수 있다.
이는 푸리에 변환과 유사하게, 그래프를 나타내는 어떤 한 signal이 주어질 때 이를 표현 가능한 어떤 함수들의 합으로 표현함으로써 그래프의 정보를 구성하는 latent 요소를 파악하는 것이다.
4-2. Spatial 방법론
Spatial 방법론은 CNN과 같이 target node의 주변 node들의 정보를 가져와서 aggregation하여 target node의 정보로 업데이트하는 방법론을 말한다. 그래프를 공간적으로 해석하는 것이 CNN의 작동방식과 유사한 점이며, 대표적으로 GCN 계열 모델이 convolution을 통해 공간적으로 해석하는 것으로 볼 수 있다.
5. 정리
두 방법론을 간단하게 정리하면 다음과 같다.
Spectral 방법론 : 그래프의 라플라시안 행렬을 고윳값 분해하여 그래프의 latent 정보 파악
Spatial 방법론 : 인접한 node의 정보를 통해 target이 되는 node의 정보를 업데이트하여 Embedding
GNN의 대표적인 모델로는 GCN, NGCF, GAT, LightGCN 등이 있으며, 해당 모델들의 자세한 내용은 추후 정리하도록 한다.
참고 1)
GNN(Graph Neural Network)의 정의와 특징 그리고 추천시스템에서의 GNN 계열 모델
들어가기 전에 이제까지 딥 러닝 모델은 CNN(Convolution Neural Network), RNN(Recurrent Neural Network), Transformer 등 다양한 신경망 모델 종류로 발전해 왔다. 그렇지만 복잡한 구조 또는 관계를 지니는 문제를
glanceyes.com
참고 2)
Graph Neural Networks 쉽게 이해하기
Graph Neural Networks 기본
velog.io
참고 3)
GNN 소개 — 기초부터 논문까지
이 글은 Shanon Hong의 An Introduction to Graph Neural Network(GNN) For Analysing Structured Data를 저자에게 허락받고 번역, 각색한 글이다.
medium.com
'DS | Data Science > ML | Machine Learning' 카테고리의 다른 글
| [ML basic] Bias & Variance (0) | 2024.01.23 |
|---|---|
| [ML Statistics] KL Divergence (0) | 2022.10.06 |
| [DL Basic] Transformer : Attention Is All You Need (0) | 2022.10.05 |
| [DL Basic] LSTM : Long Short Term Memory (1) | 2022.10.05 |
| [DL Basic] Optimization 최적화 - 3 : Regularization (0) | 2022.10.04 |