Graph Neural Network(GNN) 란? - 1

https://arxiv.org/pdf/2012.08752.pdf

 

 

현재 Neural Network는 structured 데이터에 관해 일부 분야에서 인간보다 더 잘 판단하고 추론한다고해도 과언이 아니다.

2012년이후 폭발적으로 관심을 받고 수많은 논문과 기술들이 나오면서 엄청난 정확도를 보이고 있다. 

 

Structured 데이터의 예시로는 이미지, 텍스트, 음성신호등이 있다. 이미지는 픽셀값으로 matrix형태로 나타낼 수 있고, 텍스트또한 일정한 문자를 사용한 데이터로 임베딩을 통해 유클리디안 공간에서 표현이 가능하다.

 

그렇다면 unstructured 데이터에 관해서는 어떨까? 

 

대표적으로 소셜 네트워크에서 유저들 사이의 관계는 꽤나 추상적인 개념이기에 사회적 관계망을 설명할 때 그래프는 필수적이다.

Graph Neural Network도 내 생각과는 다르게 꽤 오래전에 소개가 되었다.(2005년쯤) 하지만 인기를 얻은 건 얼마되지 않았는데, 추천시스템을 공부하면서 항상 GNN을 깊게 한번 파보자 했었는데 이제서야 시작을 하게 되었다.

이에 매주 수요일 Graph Neural Network에 관해 포스팅을 하고자 한다.

이해도 체크 겸 나중에 볼 겸 겸사겸사 기록을 해보기로 하였다.

 

총 4-5편정도로 이루어질 예정.

 

---

 

1. Graph 그래프란?

그래프란 수학이나 컴퓨터 전공인 사람이라면 익숙할텐데 그래프는 점(vertices/nodes)과 선(edges/links)으로 이루어진 데이터 구조다. 

V를 점들의 집합, E를 선들의 집합이라 할 때, 그래프는 다음과 같이 표현될 수 있다.

 

 

 

 

2. Graph Neural Network이란?

GNN(Graph Neural Network)은 단어 그대로 그래프의 형태를 가진 데이터에서 사용되는 뉴럴 네트워크다. 

GNN의 활용 예시로는 대표적으로 Node classification이 있다. ( 이외에도 Graph Classification, link prediction, clustering...)

 

이러한 여러 예시들에 쓰이는 GNN의 구조는 대표적으로 4개로 나눠질 수 있다.

 

 

1. Graph Recurrent Neural Networks

 

2. Graph Convolutional Neural Networks

 

3. Graph Pooling Operators

 

4. Graph Attention Mechanisms

 

 

3. GNN Architectures

- 3.1 Graph Recurrent Neural Networks

 

Graph Recurrent Neural Networks의 대표적인 예로는 original GNN으로 칭해지는 논문이다.

GNN을 이용하여 Node classification 하는 방식에 대해 다루었다.

 

original GNN 논문

 

Node Classification에서 각 노드 v는 feature x_v로 특징지어지고 ground truth label인 t_v와 짝지어져있다.

일부만 라벨이 주어진 그래프 G에서 목표는 라벨이 주어진 노드들을 이용해서 나머지 라벨이 없는 노드들의 라벨을 알아맞추는 것이다.(semi-supervised learning과 비슷한 맥락)

이 training 과정을 통해 다음 식과 같이 각 노드들은 d-dimensional 벡터 h_v(노드 v 주변에 대한 정보를 가지고 있는 벡터)로 표현이 된다.

 

 

https://arxiv.org/pdf/1812.08434

x_co[v] : 노드 v와 연결된 선들의 features

h_ne[v] : 노드 v의 주변 노드들의 임베딩

x_ne[v] : 노드 v의 주변 노드들의 features

f : input값들을 d-dimensional 공간으로 매핑하는 transition function 

 

 

 

---

original GNN이 Banach fixed point theorem을 기반으로 작성되었는데, thm의 내용은 다음과 같다.

(Banach 오랜만에 듣는다....)

contraction mapping의 정의

간단히 말하자면 어떠한 조건하의 매핑은 유일한 point를 갖고 모든 점에 대해 이 매핑을 무한번 적용하면 그 유일한 point로 수렴한다는 것이다.

(증명을 잠깐 보니, T가 contraction mapping인 것을 이용해 귀납법을 사용해 증명이 된다.)

 

---

 

 

이 Banach finxed point theorem을 이용하여 위의 식 

은 iterative process 형태로 다음과 같이 쓰일 수 있다.

 

https://arxiv.org/pdf/1812.08434

H과 X는 각각 위의 식에서 언급한 벡터 h, x들을 concatenation이다. (즉 Matrix H에서 node v에 해당하는 column이 h_v)

 

GNN의 output은 feature 벡터인 x_v 뿐만 아니라 위에서 계산한 임베딩 벡터인 h_v 또한 통과시켜 나오게 된다.

 

 

https://arxiv.org/pdf/1812.08434

 

앞서 나온 transition function f와 이 함수 g는 모두 feed-forwarrd fully connected Neural Networks로 해석될 수 있다.

 

또한, L1 loss는 다음과 같다.

 

https://arxiv.org/pdf/1812.08434

 

이 Loss function도 다른 네트워크처럼 gradient descent 방식으로 optimized될 수 있다.

 

 

 

그러나, 후에 이 논문에서 original GNN에 대한 한계점을 세 가지 언급한다.

 

• 만약 fixed point에 대한 조건이 완화된다면, 더 안정적인 representatio을 학습하기 위해 Multi-layer Perceptron을 사용하는 것이 가능해지고 iterative process을 생략할 수 있게 됨.

• Edge 정보를 처리하는게 불가능.(두 노드 사이에 두가지 선이면 두가지의 관계를 의미함)

• Fixed point는 노드 분포의 다양성을 저하시킴으로써 노드들의 representation을 training 하는데에 부적합함.

  

이러한 한계점들을 보완하기 위해 변형된 GNN이 몇가지 제안되었다.

 

 

 

 

- 3.2 Graph Convolutional Neural Networks

 

<다음 포스팅에 이어집니다.>

 

 

 

 

https://towardsdatascience.com/graph-neural-networks-an-overview-dfd363b6ef87

Graph Neural Networks — An overview

https://towardsdatascience.com/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

An Introduction to Graph Neural Network(GNN) For Analysing Structured Data

https://towardsdatascience.com/a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3

A Gentle Introduction to Graph Neural Network (Basics, DeepWalk, and GraphSage)