GNN을 공부하면서 적는 정리.
https://arxiv.org/pdf/1812.08434.pdf
대강 총집합해놓은 논문. 그 외 블로그 등을 참고하였음.
Intro
GNN이란 Graph Neural Network 의 준말로, 이에서 알 수 있듯 그래프 형태의 데이터(또는 Unstructured data)를 "직접적으로" 분석/학습하는데 쓰이는 네트워크이다.
최근에 GNN이 각광받는 이유는, 원래는 그래프 형태의 데이터를 해석하기 위해선 시퀀스를 또 분리하여, 연관관계 행렬을 따로 attention등으로 학습하는 등 기존의 Neural network로는 학습이 어려웠는데, GNN은 graph 형태의 input을 그대로 받아, 직접적으로 학습할 수 있어 node간의 관계를 보다 잘 학습할 것으로 관측되고, 결과를 보여주고 있기 때문이다. 다시 말해 그래프는 유클리드 공간에 없어, 어떤 차원으로 분류하기 어려운 데이터여서 기존의 네트워크로 해석이 어려웠고, 이를 GNN이 해결하려 한 것이다.
그렇다면 왜 그래프를 딥러닝에 사용하려 할까? 딥러닝은 본래 여러 파라미터들을 주어진 문제를 푸는 함수에 대해 학습시키는 것이다. 여기서 문제들에는 분류, 객체 인식, 의미 파악 등등 굉장히 많다.
이러한 함수를 구하는 과정을 뭉퉁그려서 회귀 분석이라 하는데, 곧 주어진 input과 truth간의 함수 관계를 파악하는 과정인 것이다. 하지만 보통의 시퀀스, 이미지 등은 객체 간 관계 같은 것이 주어지는 것이 아니기 때문에, 날 것으로는 학습이 어렵다. 그래서 이를 위해 우리는 input을 쪼개어 feature map으로 만들어 눈으로 확인하기 어려운 특징들을 학습시키거나, attention 메커니즘을 통해 시퀀스의 global feature를 찾아 특징을 파악한다.
그런데 만약 그래프를 학습한다면? 그래프는 보통 G = ((V,E))로서 표현되곤 한다. node와 그를 잇는 edge의 표현이다. 이 경우 객체간의 관계가, 굳이 여러운 테크닉을 적용하지 않아도 알 수 있도록 주어지는 것이다. 하지만 대신 이전에는 그래프를 당시 존재하던 네트워크로는 학습하기 어려워서 유클리드 공간으로 옮겨야만 했었다. 그래서 이러한 과정없이, 주어진 그대로 그래프를 직접 분석하는 도구인 GNN이 최근 각광받는 것이다.
그 외에도 최근 그래프로 주어지는 데이터들이 많고,(SNS 관계망 등) 크기가 큰 데이터를 줄일 수 있다는 점도 GNN의 실효성을 뒷받침한다.
서론이 길었는데, GNN의 그래프 해석 방법에는 여러가지가 있으나, 가장 맹점은 "Edge를 통해 Node를 학습한다"이다. 점들 간의 관계를 통해 점의 embedding을 학습하여 사용하는 것이다.
일례로 어떤 사람의 SNS 연결망을 친구 관계를 통해 학습할 때, 그 사람이 만약 연결된 친구(edge)가 없다면 그 사람을 학습하기 어려울 것이다. 학습할 edge가 없기 때문에 이 사람의 특징을 연결시킬 수 가 없으니, 대신 친구 수(edge 수)가 많으면 많을 수록 그 사람의 특징을 주변인 정보를 통해 학습하기 좋을 것이다.
그렇다면 어떤 방식을 통해 edge 정보로 node를 학습할까? 몇 가지 방식을 알아보자.
Recurrent GNN
이 방식은 처음 GNN이 나올 때 제안되었다고 한다. RNN과 비슷한 방식의 gate들을 사용해 node embedding을 update한다.
각 노드들을 방문하면서, 가진 edge에 따라 주변 node embedding을 학습해가는 방식으로, 이는 Banach fixed point theorem에 기초한 것이다. 해당 정리는 간단히 요약하면 어떠한 mapping T를 점에 아주 많은 반복 수를 거친다면 결국 하나의 fixed point로 거의 수렴한다는 정리이다.
그래서 각 노드들에 대해 하나의 mapping을 recurrent하게 적용한다는 이야기가 이 방식이다.
**여기선 h_v가 mapping이며, 이를 여러번 v에 적용한 뒤 (2)를 통해 output을 구했다.
실제로 여러 곳에서 많이 쓰였던 방식이고,(SR-GNN도 이 방식을 가져왔다.) 좋은 결과를 보였다.
그렇지만 단점도 있었는데, 저렇게 fixed point를 구하는 방식은 overfiting에 취약했고, 단방향/양방향 edge에 대한 정보를 무시했다.
그래서 나온 다음 방식들은 어떤 아이디어를 썼을까?
Spatial Convolutional network
-Reading
Spectral Convolutional network
-Reading