Semi-Supervised Classification With Graph Convolutional Neworks

이번엔, GCN을 준지도학습에 적용한 논문에 대해 공부해 보았다. 논문 내용을 정리해 보고자 한다.

semi-supervised learning에 대한 개념은 아래 블로그를 통해 확인할 수 있다.

https://iy322.tistory.com/11

Semi-supervised Learning

 

[논문] : Semi-supervised classification with graph convolutional networks

https://arxiv.org/abs/1609.02907

Semi-Supervised Classification with Graph Convolutional Networks

1. Introduction

citation network와 같은 graph에서의 classifying nodes(such as document)는 소수 집단의 노드에만 label이 가능하다는 문제점이 존재한다. 이는 graph 기반 semi-supervised learning(준지도학습)으로부터 형성된 문제이며, loss function에 Laplacian Regularization을 사용함으로써 발생한 것이다.

graph 기반 loss function

loss function 식에 대한 설명

위 loss function은 다음과 같은 가정에 의존한다.

Assumption: connected nodes in the graph are likely to share the same label(그래프 안에서 연결된 노드는 같은 label를 공유할 가능성이 있다.)

하지만, 위의 가정은 modeling capacity를 제한한다. graph의 edge는 필수적으로 노드 사이의 유사성 뿐만 아니라 추가적인 정보도 포함할 수 있다.

 

따라서, 논문에서는 neural network model를 graph structure에 직접적으로 사용하고 label를 가진 node를 학습시킴으로써 graph-based regularization in loss function 문제점을 해결했다. 

 

논문에서 제시한 해결방안

2. Fast Approximate Convolutions on Graphs

 multi-layer graph convolutional network(gcn) with the following layer-wise propagation rules: 

multi-layer graph convolutional network structure

[그림5] gcn 구조식에 대한 설명

 

논문에서는 multi-layer graph convolutional network structure에 대해 하나하나 설명해주었다. 수식적으로 모든 부분을 이해 못 했지만 그에 대해 스스로 최대한 이해한 데로 정리해 보고자 한다.

 

2.1 Spectral Graph Convolutions

graph의 spectral convolution siganl x와 filter g=diag(theta)를 통해 정의했다.

Spectral Graph Convoltuion Define

위의 식은 계산적으로 비용이 많이 든다. 따라서, Chebyshev Polynomials T(x)를 사용해서 근사시켰다.

Chebshev Polynomials approximation

최종적으로, graph convolutions define 식을 다음과 같이 표현할 수 있다.

with a rescaled eigenvalues

 

2.2  Layer-Wise Linear Model

위의 식을 여러개 쌓음으로써 neural network를 형성할 수 있다. 논문에서는 위의 식에서 k=1로 설정하였다.

k=1인 경우, linear function으로 표현 가능

k=1인 경우의 식을 이용하여 다수의 convolution layer를 쌓는다면 더 풍부한 표현이 가능하다. 또한, lambda(max) 값을 2에 근사시킴으로써 neural network parameter의 scale 변화를 network에 적응할 수 있도록 하였다. 

with

딥러닝 모델에서 여러번의 학습은 exploding/vanishing gradient 문제를 발생시킨다. 이를 해결하기 위해, 논문에서는 renormalization trick을 사용했다.

따라서, 최종적으로 맨 처음에 봤던 식인 다음식을 도출할 수 있다.

3. Semi-Supervised Classification

데이터 x와 graph structure를 담을 수 있는 adjacency matrix A를 활용하여 이를 가능하게 하고자 했다. 특히, adjacency matrix가 데이터 x에 대한 정보를 포함하고 있지 않을 때  강력하다.

논문에서는 two-layer GCN을 보여주었다.

위의 식을 풀어서 쓰면 다음과 같다. 

하나의 인용 네트워크 안에서 5%의 라벨만 사용해서 나머지 문서 분류에 대해서 분류

 

평가 지표로는 cross-entropy error를 사용했다.

 

이 논문을 통해 처음에 GCN이 update 되는 최종식이 도출되어지는 과정을 볼 수 있었다. 수식적으로 완벽한 이해를 하지 못한게 아쉽지만 데이터를 통해 직접 코드를 공부해면서 다시 한 번 공부해 볼 예정이다.