GNN 알고리즘 - (2) Spatial Convolutional Network

이전 글에서는 GNN 알고리즘 중 하나인 Recurrent GNN에 대해 알아보았다.

 

이전 글 :  GNN 알고리즘 - (1) Recurrent GNN

GNN 알고리즘-(1)Recurrent GNN

 

 

 

이번에 알아볼 GNN 알고리즘은 Spatial Convolutional Network이다.

 

Spatial Convolutional Network

​

이미지 분류와 이미지 영역 구분에 많이 쓰이는 Convolutional Neural Network(CNN)의 아이디어와 비슷하며 기존 convolution 방식과 거의 동일하고 graph convolution으로 표기하기도 한다.

​

간단히 말하면, 이미지에서 convolution의 아이디어는 학습 가능한 필터를 통해 중심 픽셀의 주변 픽셀을 합치는 것이다. Spatial Convolution Network의 핵심 아이디어는 이 아이디어에서 주변 픽셀 대신 연결된 점의 특징을 적용한 것이다.

​

 

Convolution on a regular graph

 

대표적인 예로 GCN(Graph Convolutional Network) 가 있다.

 

​GCN (Graph Convolutional Network) 

 

Graph Convolutional Network, 이름에서 알 수 있듯이 CNN의 특성을 접목한 GNN이다.

 

GNN 설명

 

​CNN의 특징은 다음과 같다.

 

Convolution Layer

: preserve the spatial stucture

 

 

 

예를 들어, 32 X 32 X 3의 크기를 갖는 image data가 있다고 해보자.

Convolution Filter(Kernel)라는 것을 이용하여 image를 순회하면서 dot product를 계산하고, 기존의 데이터로부터 filter를 이용하여 새로운 tensor(=activation map)를 만드는 것을 convolution 이라고 한다.

이 conv 연산의 특징 중에 하나는 바로 weight sharing이다.

Weight sharing

 

CNN에서는 filter가 image를 순회하며 연산하기 때문에 parameter를 공유할 수 있게 된다.

이런 특성을 weight sharing이라고 부르며 이로 인해 학습할 paramter 수가 적어지며, overfitting의 문제점도 해결할 수 있다.

- Reduce the number of parameter -> less overfitting, low computational cost

- Learn local features 

- translation invariance : 인풋이 조금 달라진다고 해도 웨이트가 크게 달라지지 않아서 값이 어느정도 비슷하게 나옴 

 

이처럼 conv filter를 사용하면 image로부터 어떤 feature들을 뽑아내고 activation map이 업데이트가 되면서 연산이 진행되는데, 이러한 과정을 GCN에서도 동일하게 적용하고자 한다.

What should we update?

 

CNN은 각 레이어의 activation map을 업데이트 한다.

GNN에서의 업데이트 대상은 node feature matrix(=map)이며, 이를 통해 어떤 task를 수행하는 것이 최종 목적이다.

각 node들이 갖는 feature가 업데이트 되는 것이 목표이므로 conv layer를 이용하여 feature update를 수행한다.

 

 How to update GCN

 

 

- l : l번째 layer

- Wl : l번째 레이어의 weight

- Hl : l번째 레이어의 hidden state(=각 layer를 거치고 난 뒤의 node feature matrix)

 

위의 수식이 의미하는 것은 node1의 l+1번째 node feature matrix를 나타낸 것으로

이는 node 1과 인접한 모든 node들의 node feature matrix에 각 weight를 곱하고 bias를 더한 뒤, activation function을 씌워주어 업데이트하는 과정이다.

따라서, 이 업데이트되는 과정은 convolution 연산과 같이 local한 정보를 이용하고, weight sharing을 한다는 특징을 가지기 때문에 GCN이라고 부르는 것이다.

 

여기서 모든 노드의 w가 다 똑같기 때문에 weight sharing을 가능하게 한다.

 

 

또한, 그래프의 각 node들을 업데이트 하기 위해서

해당 node의 인접한 node들의 정보, 또 그 node의 인접한 node의 정보, .... 이런식으로 다른 노드들과의 연결도 같이 고려해야 하기 때문에 이러한 connectivity의 정보를 갖고 있는 Adjacency Matrix를 이용한다.

 

각 node의 n번째 인접한(hop) node의 연결 여부를 알기 위해서는 간단하게 Adjacency Matrix를 n번 곱하면 된다.

그러면 간단한 행렬 연산으로 convolution 연산을 수행할 수 있게 된다.

 

이를 일반화시키면 아래 수식으로 나타낼 수 있다.

 

H  = AH+b

 

인접행렬 A를 곱해줌으로써 connectivity 정보가 추가되어 연결되어 있는 노드의 정보만 고려하게 됌 -> convolution과 같은 효과

 

- H의 컬럼수는 node feature 개수 

- W의 컬럼수는 convolutional layer의 filter 개수

 

relationship에 대한 정보는 A행렬이 담고 있으므로 A행렬과 H*W행렬을 곱하게 되면 최종 output행렬에서 (i, j) 가 나타내는 value는 A행렬에서 row i와 H*W행렬에서 column j를 곱한 값이다. 

 

A행렬에서 row i는 node i의 relationship정보이고 H*W행렬에서 column j는 모든 H state에 j번째 weight filter를 곱한 값이다. 따라서 이 둘을 행렬 곱한것은 기존의 모든 H state에 j번째 weight filter를 곱하고 이 중에서 node i와 relationship이 있는 state만 더한 값으로 update를 한다는 뜻이다. (Learn local feature)

 

결과적으로 최종 ouput행렬인 H'행렬에서 row i는 node i와 relationship이 있는 노드들을 각기 다른 weight filter와 연산해서 나온 value들이다. 

 

하지만 여기에 한 가지 함정이 있다.

위 그림처럼 같은 graph 구조를 갖지만 위치가 달라짐으로 인해 Adjacency Matrix가 달라지게 되는 것이다.

이러한 오류를 방지하기 위한 방법이 Readout이다.

 

CNN에서 Conv-pool layer들을 거친 후 마지막에 모든 node들 정보를 취합하기 위해 FC-layer를 거친 후 softmax를 통해 classification작업을 수행한다. 마찬가지로 Graph Neural Network에서도 graph convolution layer들을 거친 후 MLP로 모든 node 정보를 취합하고 최종적으로 regression 혹은 classification을 위해 어떤 값을 결정짓는 작업이 필요하다. 이를 GCN에서 readout-layer라고 한다.

 

Readout

 

readout은 다른말로는 Permutation Invariance라고도 한다.

- permutation :  어떤 순서로 배치되어 있는지, graph structure를 의미

 

Permutation Invariance란, 

permutation 즉 graph sturcture가 어떠하든 상관 없이 같은 위상을 갖는 graph라면 같은 결과를 내야한다는 의미이다.

 

CNN에서 Conv-pool layer들을 거친 후 마지막에 모든 node들 정보를 취합하기 위해 FC-layer를 거친 후 softmax를 통해 classification작업을 수행한다. 마찬가지로 Graph Neural Network에서도 graph convolution layer들을 거친 후 MLP로 모든 node 정보를 취합하고 최종적으로 regression 혹은 classification을 위해 어떤 값을 결정짓는 작업이 필요하다. 이를 GCN에서 readout-layer라고 한다.

 

 

이를 위해 Readout을 수행해주며, 그 수식은 그림 오른쪽과 같다.  

 l번째 node feature matrix에 대해 MLP(=fully connected) 를 씌워주고, sum 한 값에 activation function 씌워 하나의 벡터로 만든다. 

 

이렇게 하면 같은 위상에 대해서 다른 node 위치를 갖는 graph에 대해 동일한 결과를 낼 수 있다는 것이 수학적으로 증명되었다고 하며
이 Readout 방법이 가장 간단하면서도 효율적인 방법이라고 하니 기억해두자.

Overall Structure of GNN 

 

이제 GCN의 전체적인 구조에 대해 살펴보자.

 

 

 

 

위 그림과 같이, Node Feature Matrix인 X와 Adjacency Matrix인 A를 갖는 graph를 input으로 하였을 때, 원하는만큼의 convolution 연산을 거치고(중간중간에 activation function이 있긴하다.), Readout을 적용한 후 fully connected layer를 거친 후 우리가 원하는 결과를 얻게된다.

 

그렇게 나온 output과 실제 true label 혹은 true value와의 loss를 구하고 그 loss를 minimize하게끔 weight들을 업데이트 하게끔 학습이 이루어질텐데, Readout과 fully-connected layer는 우리가 흔히 아는 weight이기 때문에 설명은 넘어가고. convolution layer에서는 각 node들의 node feature들에 대한 weight를 업데이트하게 된다.

 

여기까지가 GCN에 대한 기본적인 개념을 설명한 것이고 이후부터는 GCN을 활용한 advanced model이 나온다.

 

 

다음으로는 또 다른 Convolutional 기반 GNN 알고리즘인 Spectral Convolutional Network에 대해 알아보자.

 

 

다음 글 : GNN 알고리즘 - (3) Spectral Convolutional Network

 

GNN 알고리즘-(3)Spectral Convolutional Network (Spectral methods)

 

---

참고자료

https://ganghee-lee.tistory.com/27

GNN, GCN 개념정리

https://signing.tistory.com/125

GCN, Graph Convolutional Network 설명