[ICLR 2017] Semi-Supervised Classification with Graph Convolutional Networks

PDF

GITHUB

0. BACKGROUND

Semi-Supervised Classification

Graph Convolutional Neural Network

GCN = GNN + CNN

Graph Neural Network?

Graph 꼴의 구조를 갖는 데이터에 대한 Neural Network
Graph와 관련된 모든 Neural Network를 GNN이라 칭함

Convolution on Graph

Convolution? : 두 함수의 합성곱 (이미지에만 사용되는 개념은 아님)
e.g. 종소리 예시 : 종을 연속적으로 치는 경우, t 시점의 소리는 이전 소리에 중첩된다

Graph에 Convolution Filter을 적용해 하나의 노드의 인접 노드와의 관계를 계산하고 싶어
filter로 인해 주변 node의 정보를 이용해 weight가 업데이트 되니까 local feature extraction이 가능하니까
근데 Filter들이 Spatial location에 따라 변하지 않아
⇒ Filter가 모양과 형태가 계속 달라지는데 Graph에 직접적으로 사용 가능함???!?!? NOPE
⇒ 문제점 : 일반 Convolution은 regular grid에 정의되고, 그래프상에서는 Filter가 모든 데이터에 대해 같은 크기가 아니야

참고) spatial vs spectral

Spatial : CNN 특징인 local invariance 유지해야 함 = 입력의 위치가 바뀌어도 출력은 동일함 고로 고정된 이웃 노드에서만 정보 받아서 노드 정보 업데이트

그러나, 그래프에서 한 노드의 정보는 시간에 따라 여러 노드들의 정보(signal)의 합으로 표현될 수 있음
(=message passing)

i.e. 한 노드의 정보는 여러 노드의 signal과 엮여있으므로, time domain이 아닌 frequency 도메인으로 분석한다면 한 노드 내에 섞여있는 signal을 여러 요소로 분해해 node의 특징을 더 잘 추출할 수 있을 것

= 이것이 바로 spectral graph convolution 되시겠다

Convolution Theorem

한 domain의 convolution은 다른 domain의 point-wise multiplication과 같다
= graph domain의 convolution은 fourier domain의 point-wise multiplication과 같다
convolution의 laplace 변환은 point-wise multiplication으로 변한

⇒ 그냥 간단히 말해, 합성곱 연산이 푸리에 변환(FFT)을 통한 point-wise 곱셈과 같으니, 합성곱 연산을 진행하는 대신 더 빠른 FFT를 이용해 곱셈을 하겠다

$f$와 $g$를 frequency domain으로 변환해 point-wise 곱셈을 진행하고 다시 역변환을 해 convolution을 수행하겠다

Semi-Supervised Node Classification

labeled/unlabeled node 공존
각 노드들의 feature/edge 정보 존재
labeled 데이터를 이용해 모델 훈련하고, unlabeled node 추정하기

1. INTRODUCTION

contribution

그래프 각 노드의 feature $X$와 인접 행렬 $A$가 주어졌을 때, 이를 이용하여 분류 문제를 푸는 Multi-layer Graph Convolutional Network (GCN) 제안 + 이 방법이 spectral graph convolution에 있어 매우 빠르고 효율적임
이전 semi-supervised 연구들은 $L = L_0 + \lambda L_{reg}$와 같은 loss 함수를 이용해 학습을 진행함. 여기서 $L_0$은 label에 있는 노드에 대한 loss이고, $L_{reg}$은 Graph Laplacian regularization term임. 그러나, 이는 연결된 노드는 유사하다는 가정 (동일한 label을 가질 확률이 높다)을 가지고 있기 때문에, 유사도 이외의 추가적인 정보는 존재하지 않음. GCN에서는 인접 행렬을 입력으로 이용해 어떤 노드들이 연결되어 있는지에 대한 정보를 직접적으로 이용함으로써(정규화 term 없애버리기), 이 한계 해결

2. FAST APPROXIMATE CONVOLUTIONS ON GRAPHS

GCN Network with layer-wise propagation rule

Graph를 convolution 꼴로 나타낸 식

Neural Network의 꼴로 layer를 쌓아 나타낸 식 = 최종 목표
위 식이 first-order approximation of localized spectral filters on graph인 것을 유도하는 것

2.1. Spectral Graph Convolutions

recap) Convolution Theorem에 의해 convolution을 직접적으로 수행하지 않고 다른 도메인(푸리에)의 point-wise 곱셈으로 치환

Fourier Transform

Fourier Transform
- Signal을 Frequency별로 분해하는 과정
- Time Domain → Frequency Domain
- 파란색(frequency)을 합하면 빨간색(signal)이 되는 것
- 파란색 : ‘저주파가 이정도 있고 고주파가 이정도 있다’를 히스토그램으로 나타낸 것

그럼 graph에서 푸리에 변환은 뭐임?

Graph Signal(=Graph Feature)을 Frequency(=Feature들 간의 차이)로 분해하는 것
Graph(Spatial 구조)에서 FFT 통해 frequency 도메인인Spectral 구조로 변환한 결과
그래프 노드들 간의 값의 차이가 작은(0.30)은 저주파의 값이 크고 고주파의 값이 작음
⇒ 노드들간의 유사도가 높겠군!
그래프 노드들 간의 값의 차이가 큰(5.43)은 저주파의 값이 작고 고주파의 값이 큼

Laplacian Matrix

GFT → Filtering(원하는 frequency만 필터링) → IGFT

: convolution 완성시키면서 분석에 용이한 정보만 담을 수 있을 것

= Laplacian Matrix 곱하는 것과 같음!!!

$L=D-A$
Laplacian Matrix는 두 관계를 하나의 matrix로 표현한 것
Degree matrix : 하나의 노드가 다른 몇 개의 노드와 연결되어 있는가? (대각행렬)
Adjacency matrix : 하나의 노드가 다른 어떤 노드와 연결되어 있는가? (비대각 행렬)

이때 노드의 value(feature)과 laplacian matrix가 곱해진다는 것

= 하나의 노드와 이웃 노드의 값 차이를 보겠다는 것

x1이라는 중심노드와 x2, x3이라는 이웃 노드 간의 값 차이 한번에 계산하는 것

아니 그래서 Graph Fourier Transform에서 Laplacian이 왜 등장하는데?

임의의 주파수 $f(x)$에 대하여, $\hat{f}(\xi)$는 $f(x)$와 $e^{-2\pi i x \xi}$의 내적 = 임의의 주파수 $f(x)$에 대하여, $\hat{f}(\xi)$는 $f(x)$와 $e^{-2\pi i x \xi}$가 얼마나 닮았는가
$e^{2\pi i x \xi}=cos(2\pi x \xi) + isin(2\pi x \xi)$ (오일러 공식)
고로 주어진 주파수 $f(x)$에 대해 cos에서 유사한 정도와 sin에서 유사한 정도의 합이 푸리에 변환이다
이때, 선형대수에서, 벡터 a를 d차원의 orthonormal basis를 찾을 수 있다면, 벡터 a를 orthonormal basis의 선형결합으로 표현할 수 있다. 이 orthonormal basis를 찾는 방법 중 하나가 바로 eigen value decomposition!
결론 : 어떤 특정 graph signal에 대한 행렬이 존재하고, 이 행렬이 symmetric matrix이며, 이들의 eigen vectors를 구할 수 있다면, eigen vector의 선형결합이 graph signal의 푸리에 변환이다.
이때 laplacian matrix 선형대수적 성질😇
- positive semi-definite
- 모든 eigenvalue가 0보다 크다
- eigen decomposition의 diagonal entry가 0보다 크다
- N개만큼의 eigenvalue-vector pairs가 존재한다

뭐 대충 설명하자면, Fourier Transform을 할 때 laplace operator가 쓰이는데, laplacian eigen vectors가 이 fourier basis 역할을 함

어쨌든 결론은 Laplacian matrix를 feature vector에 곱하는 것이 Fourier Transform의 역할을 함
빨간 네모는 laplacian eigen decomposition 한 것
decomposition을 통해 $\lambda$가 작은 순으로 sorting하게 되고, eigen value가 작은(=frequency가 작은) eigen vector로 FFT 한다는 것은, 중심 노드와 차이가 작은 노드들 간의 관계만 반영한다는 것

잠시 딴 말)

eigen 친구들 PCA에서 자주 등장했었는데 PCA랑 비교한다면 더 잘 이해할 수 있을지도

PCA : 분산 최대화 = 최대한 많은 정보를 보존하겠다

GFT : 최대한 frequency가 적은 관계만을 가져오겠다.

여기까지 문제점