[Advanced ML & DL Week1] Semi-supervised Classification with Graph Convolutional Networks

작성자: 15기 이병주

 

1. Graph Convolution (그래프 합성곱)

그래프에 convolution filter를 적용하여, 노드 하나와 인접 노드와의 관계를 계산하고 싶음.

convolution on graph

그래프에서 convolution이 어려운 이유

• convolution은 regular grid에서 정의됨
• filter의 크기가 다 다르다. 

 

Convolution Theorem

the convolution of two functions in real space is the same as the product of their respective Fourier transforms in Fourier space

그래프에서 convolution은 푸리에 point-wise multiplication과 같다!

 

 

2.  Node Classification

주어진 것

• labeled, unlabeled 노드가 있는 그래프
• 노드들의 feature 정보, edge 정보

 

supervised 로 모델 훈련시키고 inference는 unlabeled data 

 

3. Introduction

L0 : labeled 에 대한 supervised loss

X : matrix of node feature vectors Xi .

∆ = D − A

가정 : 연결된 노드들은 같은 label일 가능성이 높다. 

그러나 연결된게 similarity 이상의 정보를 담을 수 있음

 

4. Graph Fourier Transform

 

푸리에 변환

 

graph signal을 frequency로 분해하는 과정

 

signal : 노드의 feature

frequency: feature들 간의 차이

  

5. Spectral Graph Convolutions

spectral convolution을 signal x와 filter gθ 의 합성곱으로 정의

U : the matrix of eigenvectors of the norma lized graph Laplacian

x의 앞부분은 Laplacian matrix의 eigen decomposition과 같다. 

Adjacency matrix

노드가 누구와 연결되어 있는지 

연결되어 있으면 1, 연결안되어 있으면 0 

 

Degree matrix

해당 노드가 몇 개의 노드랑 연결되어 있는지

대각 행렬

 

Laplacian Matrix

L = D − A

 

 

결론 : Laplacian 을 feature vector 에 곱하는 것이 푸리에 변환의 역할을 한다.

 

여기까지의 문제점

• 전체 eigen value를 다 사용해서 localized 되지 않았다.
• eigen decomposition의 계산량이 너무 많다.

 

localized filter 로 만들기 위해 polynomial parametrization(다항식으로 근사) 을 시행 

k= 한 노드의 이웃의 범위로 지정

이것도 아직 계산량이 많아서 근사식을 활용! (chebyshev polynomial)

 

GCN은 k=1로 변환하여 해당과정을 layer로 표현

 

6. SEMI-SUPERVISED NODE CLASSIFICATION (2 layer convolutional neural network)

 

A: adjacency matrix

X: data

 

W(0) : input ----> hidden 의 weight matrix

W(1) : hidden ---->  output 의 weight matrix

 

loss function

yL : labeled data 에서만 표현

 

7. Experiment

노드: 논문

edge: 인용

노드 feature: bag of words