GNN 공부

이두현·2022년 3월 8일

GNN의 등장은 non-euclidean space 의 data를 처리하기 위함이라고 한다.

euclidean space는 우리가 흔히 아는 $R^n$ 으로 정의된 linear space 를 의미한다.
논문에서 명시된 non-euclidean space는 이러한 방식으로 표현이 불가능한 data 들이 놓여있는 공간을 의미한다.
예를 들어 node와 edge가 존재하는 사회 신경망을 표현하는 그래프를 n dimensional linear space로 옮겨오고 싶은 경우 그래프의 방향, weight등이 embedding 과정에서 손실될 수 있다.
명확한 mapping 방법이 존재하지 않는 이러한 데이터들에 대해 GNN은 이들을 input으로 쉽게 처리하고자 하는 동기부여를 통해 생성되었다.
https://ai.stackexchange.com/questions/11226/what-is-non-euclidean-data

초기 각 노드는 자신에게 주어진 initial value vector를 갖고 있지만 GNN을 통과한 이후에는 그 노드가 주변에 어떻게 속해있는지 나타내는 vector를 갖게 된다.

Neural message passing
timestep t-1에서 F 노드의 distributed vector가 $h_{t-1}$ 이었다면 다음 timestep으로 업데이트 되기 위해서 아래와 같은 과정을 거친다.

정의된 함수 f는 각 출발 노드 (D,E)에 대한 정보와 egde 정보, 그리고 도착 노드(F)에 대한 정보를 받아 output을 내는데 그 형태도 vector이다. (위의 그림에서 message로 표현된 부분)
이렇게 생성된 vector들을 원래 F 노드를 represent하던 vector인 $h_{t-1}$ 과 적절한 방식으로 조합해 현재 timestep에 맞는 $h_t$ 로 업데이트한다.
매 timestep 마다 각 노드는 위와 같이 인접한 노드로부터 vector 정보를 input으로 받아 자신의 distributed vector를 업데이트한다. 다음 timestep 에서는 어떤 노드의 인접 노드들도 자신의 인접 노드의 정보를 받아 업데이트 한 상태이므로 이번엔 distance 하나가 증가한 인접 노드들에 대한 정보를 배우게 될 것이다. (시간이 지날수록 distance가 점점 증가)
GNN을 통과한 node output으로 할 수 있는 것들

Node classification

GNN 결과로 나온 각 노드에 대한 distribution vector를 single layer에 통과시킨 후 0,1 판별 Loss를 적용한다.
gated GNN

위에서 설명한 것과 같이 어떤 노드에 인접한 노드들에 대해서 edge와 distributed vector 간의 곱을 더해 m 이라는 term을 update의 대상이 되는 node의 distribution vector update에 사용하는데 GRU(Graph Recurrent Unit)를 사용하는는 방식을 의미한다.
GGN - Graph Convolution Network
$h_{t-1}$ 에서 $h_t$ 로 업데이트 하는 과정에서 Convolution layer를 사용하는 방식을 의미하며 아래와 같은 식으로 업데이트 된다.
$h_t^n=\sigma(\frac{1}{neighbors+1}W_t(h_{t-1}^n+\sum h_{t-1}^{n'}))$

backward edge
어떤 노드로 들어오는 egde 정보가 없을 경우 위의 알고리즘으로는 그 노드가 어떻게 graph에 속해있는지 배울 수 없기 때문에 모든 forward edge들에 대해 backward edge를 추가하여 모든 노드에 대해 빠짐없이 배울 수 있도록 만들어준다.

0100101