[Paper] GNN

“The Graph Neural Network Model”이란 논문에 대한 리뷰입니다.

원문은 링크에서 확인할 수 있습니다.

Background

목적에 따라

• Graph-focus의 경우 node와 무관히 일종의 classifier를 사용합니다.
• Ex. Chemical compound
• Node-focus의 경우 node의 property에 영향받는 classification을 진행합니다.

그리고 이전까지의 연구는 graph를 vector로 processing을 하여 사용하여서 topological dependency를 반영하지 못하였고, 문제는 underlying graph structure를 encoding하는 것이라고 합니다.

• Related Work

RNN / Markov chain이 대안으로 제안

• RNN의 경우 SVM과 같은 것에 special kernel을 사용
• Ex. Diffusion kernel  heat diffusion equation 바탕으로 random walk의 결과에서 common element 수를 사용하는 방식
• Markov chain의 경우 random walk theory를 사용
• Ex. Random field, Bayesian Net, statistical relational learning, transductive learning, 등등 제안

GNN이란?

1. extension of RNN & random walk
2. information diffusion mechanism 바탕
3. 각 유닛들이 state 업데이트와 information exchange 후 equilibrium 도달
4. 이를 보장해주는 것이 Banach fixed point theorem

이는 한 unit의 state를 정의하는 식으로 한 state는 incident한 edge와 vertex의 label과 state로 정해지는 것으로 판단하게 됩니다.

이를 일반화시킨 것이 다음식입니다. 위의 식에서 F는 global transition function으로 이전 state에 대한 정보와 관련된 label 정보로 해당 unit의 정보가 어떻게 transition이 일어나는지 설명하고 있습니다.

여기서 G는 output을 연산하기 위한 식으로 정리되고 구조는 다음과 같습니다. 위의 구조에서 보면 알 수 있듯이 일종의 RNN처럼 처리하게 되어있습니다.

본 논문은 GNN이란 개념과 관련된 수학적인 서술이 매우 잘 서술되어 있어서 추천하는 논문입니다.