그래프 자료 구조는 일반적으로 이미지나 텍스트와 달리 그 구성이나 형태, 밀도(density) 등이 매우 다르다는 특성이 있습니다. 이미지나 텍스트도 여전히 비정형 데이터(unstructured data)이긴 하지만, 적어도 사람이 주로 사용하는 것들은 그 범위가 일반적인 수준에서 크게 벗어나지 않습니다. 예를 들어, 이미지에는 노이즈와 같이 의미 없는 픽셀 값들이 아닌 특정한 대상(object)이 있을 것으로 예상하며, 텍스트는 무작위한 글자의 나열이 아닌 의미가 있는 특정한 순서에 의한 단어들의 나열을 기대합니다. 그런데 그래프나 네트워크 자료 구조는 그렇지 않습니다. 지식 그래프(Knowledge Graph)와 소셜 네트워크(Social Network), 단백질 분자구조(Protein Structure)는 그 형태가 완전 다를 것입니다. 따라서 그래프 분석에서는 특히나 일반론적인 방법을 찾는 것이 매우 어렵습니다.
뉴럴 네트워크를 이용한 GNN들의 구조들은 기존 이미지나 텍스트 등에 사용되어 왔던 구조들을 차용해서 사용합니다. 큰 분류를 나열하면 아래와 같습니다.
Types of GNNs
Recurrent는 말그대로 RNN 계열을 사용한 모델로, 특정 노드에서 출발해 이웃한 노드로 이동해가며 기존까지 누적된 $h_{t-1}$의 정보와 현재 노드의 feature $x_t$를 바탕으로 새롭게 $h_t$를 업데이트하는 방식입니다. 노드들을 순차적으로 이동하는 것을 time step처럼 간주한다는 점에서 기존 time-series나 language modeling에서 사용되는 것과 유사합니다. 이 경우 n-th order neighborhood를 한 번에 포괄하여 local feature뿐만 아니라 global feature 관계를 계산할 수 있습니다.
Convolution 계열은 앞에서 말한 것과 약간 반대로, first-order neighborhood를 포괄하게 됩니다. 즉, local feature를 포착하는데 특화되어 있습니다. 따라서 여러 층을 깊게 쌓아서 second-order 이상의 관계를 보는 네트워크를 만들 수 있습니다. 이에는 Spectral GCN과 Spatial GCN으로 나뉘는데, 이는 이어서 다루겠습니다.
Graph Autoencoder는 Autoencoder가 대표적인 generative model이듯이, 그래프의 분포를 implicit하게 배우게 됩니다. 이 경우 새로운 신약 물질이나 단백질 구조를 생성하는 모델로 활용할 수 있겠죠? 또한 마지막으로 Spatial-Temporal GNN은 spatial한 structure뿐만 아니라 시간에 따라 변화하는 dynamics를 담아낼 수 있는 구조입니다.
Convolution 연산은 아래와 같은 식으로 쓸 수 있습니다.
$$ f * g = (f * g)(t) = \int f(\tau) g(t-\tau) d\tau $$
이때 Graph convolution은 graph에 convolution filter를 사용하여 하나의 node와 neighbor nodes와의 관계를 계산하는 것을 의미합니다. 따라서 convolution은 local feature를 포착하는 데 매우 유용하며, 이미지나 음성에서와 마찬가지로 filter들이 spatial location에 따라 달라지는 것이 아니라 동일한 필터를 이동시키며 적용하게 됩니다.
그렇다면 Spectral convolution과 Spatial convolution의 차이는 무엇일까요? 일단 공통적으로 목적은 동일합니다. Central node의 feature를 neighbor nodes들의 feature를 이용하여 업데이트하는 것입니다. 이는 거리가 가까운 노드들끼리는 유사할 것이라는 그래프의 기본적인 가정사항으로부터 출발합니다. 그래프뿐만 아니라 자연어 처리, 컴퓨터 비전 등 태스크에서도 유사한 가정들이 있는데요, 해당 가정사항들을 간과하고 모델을 이해했을 때 핵심을 놓치게 됩니다. 예컨대 자연어 처리에서는 이웃에 등장하는 단어들끼리는 의미가 유사할 것이라는 것(distributional hypothesis), 컴퓨터 비전에서는 특정 픽셀과 이웃한 픽셀이 유사한 시각적 정보를 담고 있을 것이라는 가정입니다.
둘의 가장 큰 차이점은 Spectral convolution은 graph를 signal processing의 한 종류로 보며 graph signal에 대한 noise를 제거하는 과정으로 인식한다는 것입니다. 이는 Fourier tranformation에서 frequecy의 spectrum에서 원하는 frequency만을 filtering하는 것과 유사합니다. 반면에 Spatial은 CNN에서 본 것과 같이 인접한 노드들로부터 정보를 update하는 직관적인 구조를 갖습니다. 그렇다면 왜 spectral convolution을 사용하는 것일까요?
가장 큰 이유는 수학적 기반이 더 탄탄하기 때문이라고 합니다. 그래프 이론 쪽에서 Spectral Graph Theory는 그래프 연구에서 상당한 비중을 차지하고 있습니다. 한편, 컴퓨터에서 연산이 이뤄지는 과정에서 Spatial GCN은 그래프에서 이웃한 노드들이 물리적 메모리 공간상에서는 이웃하지 않기 때문에 비효율이 발생하게 됩니다. 반면에 Spectral GCN은 Fourier transformation과 inverse Fourier transformation을 이용하여 matrix 연산만으로 구할 수 있어 연산에서 훨씬 효율적이라는 큰 강점도 존재합니다.
Convolution Theorem 중에는 아래와 같은 내용이 있습니다.