[Paper] Spatial GNN

“Neural Network for Graphs: A Contextual Constructive Approach”이란 논문에 대한 리뷰입니다.

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

NN4G

Challenge 1

• transition system의 causality의 문제를 해결 이는 directed acyclic graph에서 한 vertex에 대한 computation은 current vertex와 이전 vertex가 영향을 끼치게 되는 현상을 말하는 것으로 생각한다. 즉 iterating시켜서 update하는 것을 말하는 것이지 않을까

Challenge 2

• Cyclic graph를 다루는 문제 즉, graph의 class에 따라서 적용이 달라지는 것이 문제임을 말한다. 그래서 contextual processing이라는 과정을 통해 해결하였다고 제안

Challenge 3

• RNN 구조에서 학습이 어려운 것을 지적

하나의 graph를 여러차례 학습하는 것이 Hidden Unit이 점점 쌓이게 되는 방식이며 이와 같은 구조를 통해 neighbor가 state를 정의하는 데에 사용이 되어서 spatial이라고 불리는 것으로 생각한다.
기본적으로 graph라고 하는 것이 RNN 기반에서 논의가 많이 되어서 이렇게 작성된 것으로 생각된다.

Contextual processing에서 중요한 것은 local의 neighborhood를 input으로 사용하여 progressive하게 진행되는 것이다.

아래의 식은 첫번째 그림에서 하나씩 진행이 되는 단계가 된다. Hidden unit의 일종의 layer가 증가할 수록 term이 증가하는 형태라서 constructive network라고 말하는 것 같다.
그리고 3가지의 w들(w-bar, w-hat, w-oh)들이 결국 estimate하여 error를 minimize하게 되는 것.

구조는 사실 NN과 동일하며 중요한 것은 이전 unit들은 constant로 두고 현재의 parameter들만 업데이트 하게 된다.
또한 특정 error 수준까지 도달할 때까지 hidden unit의 개수를 늘려서 dimension이 증가하게 된다.

알고리즘

obejective

중요한 것은 단순히 error를 minimization하는 것뿐만 아니라 Hidden unit과 residual error of the output과의 correlation을 maximization하는 criteria를 사용한다.