7. Graph Neural Network(GNN)

안녕하세요. 조쉬입니다.

오늘 다뤄볼 내용은 Graph Neural Network입니다.

 

1. 개요

 

source:https://digi.uga.edu/network-graphs/

Graph란 정형 데이터와 비정형 데이터와는 또 다른 형태의 데이터 구조입니다.

주로 개체 사이의 연관성이 중요한 요소로 떠오를 때 고려할만한 구조로서 관계나 상호작용을 분석할 때 쓰이게 됩니다.

대표적인 예시로는 페이스북 유저 간의 관계, 분자 구조 내의 원자 간의 관계 등을 표현하는 구조로 사용이 되고 있습니다.

---

2. 데이터 특성

Graph는 데이터 구조상 Node와 Edge의 두 가지 요소를 포함하게 됩니다. Node는 개체의 특성을 대표하고 Edge는 개체 간의 연결성을 나타냅니다. 

Graph는 주로 G = (V, E)라고 정의가 됩니다. 여기서 V는 Node, E는 Edge에 관한 정보입니다. 보통 Edge내의 연결 고리는 방향성을 가지는 경우가 많으므로 해당 정보도 E안에 표현이 됩니다.

Graph 구조는 adjacency matrix로도 표현이 가능하게 되는데, n개의 Node를 포함한 구조를 가정한다면 adjacency matrix는 n * n 차원을 구조를 띄게 됩니다.

source : https://www.researchgate.net/figure/Different-types-of-graphs-and-their-corresponding-adjacency-matrix-representations-The_fig1_347300725

Adjacency Matrix란 node 간의 연결 관계를 나타내 주는 matrix로서 상기 그림과 같이 표현하여 사용합니다. Identity 값들은 각 노드로의 루프 경로가 없기 때문에 0으로 설정이 되어있는 것이 확인됩니다. 

 

만약 node내에 f개의 feature가 포함이 되어있다면 node matrix는 n * f 차원을 띄게 됩니다. 이는 기존의 정형 데이터의 형태와 동일하다고 이해하면 됩니다. 

 

source : https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications

Graph 데이터와 정형 & 비정형(이미지, 텍스트)의 차이점은 데이터 구조의 고정성입니다. 정형 데이터의 경우 피쳐의 수가 고정이 되어있고 image의 경우 grid 수가 고정이 되어있으며 text의 경우 token length가 고정이 된다는 특징이 있습니다. 하지만 Graph 데이터의 경우 node가 정렬되어있지 않고, node 간의 연결된 이웃들의 개수도 다를 수 있다는 차이점이 있습니다. 

 

또한 보통 머신러닝 기반의 알고리즘들이 개체 간 독립성을 가정하고 학습과 예측을 진행하는 점도 Graph 구조의 분석에 방해가 되는 요소입니다. 

 

이러한 특징들을 다 제쳐두고 우리가 Graph 데이터 구조와 모델을 사용해야 하는 이유는 과연 무엇일까요?

1. 개체 간 상호작용에 대한 직간접적 분석이 가능해진다.

2. 데이터 구조의 변경으로 새로운 접근이 가능하다.

3. 연결성이 중요시되는 데이터(ex. 소셜 데이터)에 대한 활용성이 크다.

 

3.  Graph Neural Network

3.1 Embedding

Graph 이론에서 node embedding을 적용할 수도 있습니다. 노드를 유사도 기반으로 mapping 하여 네트워크 내 개체 간의 유사도를 산출하는 방식입니다. 

source : https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications

여기서 embedding을 진행하는 encoder는 다음과 같은 특성을 가져야 합니다.

1. locality

2. 정보 집계성

3. 다중 layer 중첩성

 

로컬 정보는 computational graph를 생성하여 산출할 수 있습니다. 하단 그림에서와 같이 "i"라는 node가 주변 node들과 어떻게 관계를 가지고 있고 또 그 주변 node들은 어떤 관계가 있는지 모든 연결 지점들을 계산하여 computational graph를 생성합니다. 이러한 과정에서 네트워크의 구조를 파악할 수 있게 됩니다.

source : https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications

local 정보를 전부 저장한 computational graph를 딥러닝 기법으로 집계하여 활용을 하게 됩니다.

 

이때 주로 사용하는  back propagetion이 아닌 forward propagation을 사용하게 됩니다. 이 방식은 인풋의 정보가 어떠한 방식으로   산출 값으로 나오게 될지 결정하게 됩니다.

모든 노드는 피쳐 벡터를 가지게 됩니다. 피쳐 벡터를 모델의 인풋으로 지정하여 두 개의 피쳐 벡터를 동시에 입력받아 집계를 하여 다음 레이어로 값을 넘겨주게 됩니다. 노드 A의 입력값이 노드 A의 피쳐라면, 노드 A의 layer 1 representation은 hidden, latent representation이 됩니다. 그리고 layer 2는 또 다른 latent representation입니다.

 

해당 내용은 unsupervised, supervised 두 가지 방법으로 진행이 가능하며 loss function에 의한 stochastic gradient descent로 학습이 됩니다.

 

- unsupervised train

unsupervised loss function은 node proximity이나 random walk에 기반한 함수로 활용이 가능합니다.

 

- supervised train

분류 또는 회귀, 이상치 탐지 등의 방식으로 task 진행이 가능합니다.

 

3.2 Graph Convolutional Networks

“Spectral Networks and Deep Locally Connected Networks on Graphs” (Bruna et al, 2014)에서 처음 소개된 모델로 neural network 구조를 graph structured data에 적용하는 방식입니다.

 

GCN은 세 가지 구조로 구성되어있습니다.

1. Graph convolution

2. Linear layer

3. Nonlinear activation

 

상기 3개의 함수가 하나의 레이어에 통합되는 구조로서 여러 레이어를 적층 하여 사용할 수 있습니다. 

 

3.3 GraphSAGE idea

GraphSAGE는 dynamic graph를 위한 representation learning 방식입니다. 이 방식은 재학습 절차를 생략하고, 새로운 노드의 임베딩을 예측할 수 있습니다.

 

이러한 방식을 위해, GraphSage는 귀납적 학습 방법을 차용했습니다. 이 방식으로 노드의 피쳐와 이웃 간의 관계를 통해 노드의 임베딩을 유도하는 집계 함수를 학습하게 됩니다.

 

노드 개별 정보와 이웃 간의 정보를 합치는 것이 아닌 각자 다르게 처리하여 concat 함으로 서 정보의 독립성을 유지한다고 볼 수 있습니다.

 

집계 함수로서는 평균치 활용, pooling, 또는 lstm을 통한 sequence 한 정보 추출 방식 등이 활용될 수 있습니다.

 

 

4. 활용 방안

4.1 노드 분류 : 이 task는 샘플의 label을 결정하는 방식으로 이웃의 label을 확인하는 방식으로도 진행할 수 있습니다. 보통 이러한 방식은 semi-supervised 방식으로 진행되며 pre-labeled 된 그래프를 통하여 활용될 수 있습니다.

 

4.2 Graph 분류 : 이 task는 graph 자체를 카테고리로 분류하는 방식입니다. 이미지 분류 방식과 비슷하지만 graph 도메인에서 작동한다고 보면 이해가 쉽습니다. 생명공학 도메인에서 단백질 구조 분류 또는 NLP에서 문서 분류 또는 social network 분석에서 활용 가능합니다.

 

4.3 Graph 시각화 : graph 자체를 시각화 함으로써 유저가 graph를 이해하도록 데이터를 표현하는 것에 집중된 방식으로 구조 분석이나 이상치 탐지에 활용됩니다.

 

4.4 Link Prediction : 이 방식은 graph내의 노드 간의 관계를 이해하는 것에 중점을 두어 랜덤 한 두 노드 간에 관계를 예측하는 데에 활용됩니다. social network 내의 유저 간 관계 예측에 활용이 되며, 추천 시스템 또는 범죄 예측에 활용이 됩니다. 

 

4.5 Graph Clustering : graph 내의 군집 분류를 목적으로 하는 방식으로 밀집하여 연결된 노드 간의 엣지의 weight와 거리를 분류해 냅니다. 노드 간의 유사성을 판단하여 graph의 내용을 단순화하여 표현해내는 것에 초점을 두는 방식입니다. 

 

5. Reference

- https://neptune.ai/blog/graph-neural-network-and-some-of-gnn-applications

Graph Neural Network and Some of GNN Applications: Everything You Need to Know - neptune.ai

- https://jonathan-hui.medium.com/applications-of-graph-neural-networks-gnn-d487fd5ed17d

Applications of Graph Neural Networks (GNN)

- https://data-newbie.tistory.com/718?category=884325 

GNN - Application 및 샘플 코드

- https://medium.com/watcha/gnn-소개-기초부터-논문까지-96567b783479

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

- https://towardsdatascience.com/introduction-to-deepminds-graph-nets-b389430476fd

Introduction to DeepMind’s Graph-Nets