Graph Convolutional Networks (GCN)

Kipf and Welling (2017)가 소개한 Graph Convolutional Networks (GCN)은 Graph Neural Networks (GNN)의 한가지 변형이라고 할 수 있다.

 

GCN에서는 흔히 fileters나 kernels로 알려진 weights과 input을 곱한다라는 Convolutional Neural Networks (CNN)에서의 'convolution'의 개념이 동일하게 사용된다. CNN에서 각 layer들은 각각의 filter를 갖고 하나의 layer에서 해당 layer의 filter, 즉 하나의 filter가 전체 이미지를 훑으며 연산과정을 거치는데 이 과정을 weight sharing이라고 한다. GCN 이웃한 nodes를 함께 연산한다는 점에서는 CNN과 비슷한 진행과정을 갖으나, 그래프는 이미지와는 달리 nodes들의 연결 개수가 다양하고 고정되지 않은 형태를 가지고 있다 (non-Euclidean structured data) 는 것이 CNN과의 가장 큰 차이점이다.

 

 

GCN은 크게 Spatial GCN과 Spectral GCN, 이렇게 2가지의 네트워크 형태로 나뉠 수 있다.

Spatial Graph Convolutional Networks

그래프의 nodes를 이미지의 pixels로, 각 pixel의 값들을 node의 features라고 볼 때, 주변 pixels들의 값들을 연산한다는 CNN의 기본아이디어와 같다. 이웃한 nodes들의 features를 합하여 centre nodes로 보낸다는 것이다.

 

 

 

Spectral Graph Convolutional Networks

Spectral GCN은 다른 타입의 GNN보다 상대적으로 많은 수학적 토대에 기초한다.

Kipf and Welling (2017)는 아래의 식으로 묘사되는 2-layered neural network structure을 제안하는데, 이는 흔히 사용되는 2개의 fully-connected layer structure와 동일하다.

$$Z = f(X, A) = \text{softmax}(\hat{A}\text{Relu}(\hat{A}XW^{(0)})W^{(1)})$$

• $X$: nodes의 feature matrix
• $\hat{A}$ : 전처리된 Laplacian of original Graph Adjacency Matrix $A$
• $W^{(0)}\in \mathbb{R}^{C\text{x}H}$: an input-to-hidden weight matrix for a hidden layer with features $H$
• $W^{(1)}\in \mathbb{R}^{H\text{x}F}$: a hidden-to-output weight matrix

 

다음과 같은 하나의 그래프를 예시로 들어보자.

Adjacency Matrix $A$

Adjacency matrix를 생성할 때, 각 노드는 자기 자신과의 연결을 가정하여 (Matrix에서 빨간색으로 쓰여진 요소들), feature aggregation이 진행되면서 자기 자신의 features도 함께 합하여 지도록 한다.

Feature Matrix $X$

 

Matrix $H$는 두 matrices $A$와 $X$의 곱으로 생성된다.

 

$A \times X = H$

$h_{1,1} = A_{1,1}X_{1,1} + A_{1,2}X_{2,1} + A_{1,3}X_{3,1} + A_{1,4}X_{4,1}$

$h_{1,2} = A_{1,1}X_{1,2} + A_{1,2}X_{2,2} + A_{1,3}X_{3,2} + A_{1,4}X_{4,2}$

$h_{1,3} = A_{1,1}X_{1,3} + A_{1,2}X_{2,3} + A_{1,3}X_{3,3} + A_{1,4}X_{4,3}$

 

 

 

그러므로, Spectral GCN과 Spatial GCN은 서로 다른 아이디어로 convolution연산을 시작했을지라도 결국 같은 전파 법칙 (the propagation rule)을 땨른다고 볼 수 있다. 뿐만 아니라 모든 GCN은 massage passing process를 통하여 node information을 전달하고 node를 update하는 함수를 학습하는 것과 같은 형식을 따른다.

 

 

 

Reference

• Semi-Supervised Classification with Graph Convolutional Networks
  https://arxiv.org/pdf/1609.02907.pdf
• Understanding Graph Convolutional Networks for Node Classification
  https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b
• Getting the Intuition of Graph Neural Networks
  https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b
• A Comparative Survey on Graph Neural Networks
  https://arxiv.org/pdf/1901.00596.pdf