Graph Neural Network

Graph Neural Network

- NN에서 Input의 형태가 그래프일때 사용하는 Neural Network

- Fully-connected network, CNN (Convolutional Neural network), RNN (Recurrent Neural network)의 경우 보통벡터나 행렬 형태로 input이 주어짐

- GNN의 경우에는 input이 그래프 구조라는 특징이 있음 (ex. 영상에서의 graph, 분자구조 graph, Social graph ...)

Graph를 Neural Network에 태워서 뭘 하려 하는가?

1. Node classification 

- 어떠한 노드가 어떤 그룹으로 묶일 것인가 (클러스터링)

2. Link prediction

- 노드와 노드가 친구가 될 수 있을까? 친구 추천

- 얼마나 친한지를 나타내는지

3. Feature Prediction

- 새로운 어떤 연결 정보가 들어왔을때 나(노드)의 정보가 어떻게 바뀔지 예측하는 것

Graph data

-  Graph = (node(vertex),edge)

1) Adjacency matrix

- node간의 연결(relationship)정보

- 보통 나 자식과의 관계는 diagonal matrix(1)를 더해줌

- ex. Social Graph에서 두 사람간의 relationship 정보 - 친구관계인지 아닌지)

2) Feature matrix

- node(input data)자체가 가지고 있는 feature 정보

- ex. Social Graph 에서 한 명의 사람이 갖고 있는 정보 - 이름, 나이, 국가, 학력, ... )

Graph Structure

1) Network(Graph data) 에서 Adjacency matrix를 만드는 방법

a. 위 그림에서 가장 좌측에 있는 그림과 같은 Network가 존재할때 n개의 node를 n*n matrix로 표현

b. 이렇게 생성된 Adjacency matrix내의 value는 (Aij=i와 j의 relationship 여부)를 만족하는 value

2) Feature matrix를 만드는 방법

a. 각 input data에서 이용할 feature를 먼저 select한다. (ex. RGB값 3개, transparency 1개, ... )

b. Feature matrix에서 각 row는 선정한 feature에 대해 각 node가 갖는 값을 의미한다. (ex. row1=node1의 feature값들)

 

Graph Neural Network에서 학습되는 방법

1. Feature Matrix와 초기 weight matrix를 곱해줌

2. 주변 노드의 정보를 가져오기 위해 Adjacency Matrix를 곱해줌

- 2번 노드의 경우는 1번 노드와 연결되어 있고, 3,4번 노드와는 연결되어 있지 않기 때문에 삭제됨

3. 위와 같은 방법으로 전체 노드에 대해 지역적으로 연결된 노드간의 정보를 통해 업데이트하면 아래와 같이 업데이트가 됨 

- 이렇게 한번 전체적으로 지역적 노드와 같이 업데이트 되는 형태를 1회의 layer를 거쳤다라고 표현

4. 계속해서 layer를 타면서 업데이트를 하다보면 하나의 노드에는 더많은 feature 정보를 담게 됨

CNN의 구조와 같이 layer를 거칠수록 중요 정보를 담은 것을 가지고 감

---

 Readout layer가 필요 이유

- 같은 Network를 갖는 두 Graph가 Adjacency matrix는 서로 다를 수 있음 

- 즉, 모든 node간의 edge정보가 같아도 회전, 대칭에 의해 행렬내 값의 순서 변화

- 예를 들면 같은 사진이라도 회전하고 대칭에 따라 matrix가 다른 케이스가 있다고 이해하면 됨

- 위 문제를 풀어 주기 위해 readout layer를 두어서 같은 graph인 것을 확인하고,

- 같은 Graph이지만 Adjacency matrix가 다른 경우, Permutation에 대해 invariance하도록 하기위해 MLP를 곱하는 readout-layer가 필요

 

 

참조

https://greenmon.dev/2020/06/13/GNN-basics.html

GNN 사용을 위한 넓고 얕은 지식

https://jxnjxn.tistory.com/77

[CS224W] 8. Graph Neural Networks

https://www.youtube.com/watch?v=9eMbvfRM9_8&list=LL&index=1