GCN 논문 리뷰_Semi-Supervised Classification With Graph Convolutional Networks

GCN = GNN + CNN

GNN과 CNN을 합친 형태인데 각각에서 어떤 것을 취했는지 알아보겠다.

 

먼저, GNN(Graph Neural Network)에 대해 알아보겠다.

GNN은 연결관계와 이웃들의 상태를 이용하여 각 노드의 상태를 업데이트하고 학습한다. 그리고 학습된 마지막 상태가 최종 노드 임베딩이 된다. GNN은 크게 (1)Recurrent GNN, (2)Spatial Convolutional Network, (3)Spectral Convolutional Network 이 세 가지 유형으로 나눌 수 있다. 이 중에서 (3)Spectral Convolutional Network가 수학적 기반이 있기 때문에 더 잘 쓰이고 GCN 또한 이 기반이다. Spectral Convolutional Network는 그래프 신호 처리 이론을 기반으로 고안되었으며 Spectral은 Spectrum을 의미한다. Frequency의 스펙트럼에서 원하는 스펙트럼을 필터링한다고 생각하면 된다.

(그래프에 대해 Signal/Filter의 개념을 적용하기 위해 Graph Fourier Transform이 사용되어야 한다. 이를 더 깊이 이해하기 위해서는 DSBA 연구실의 GCN 세미나 영상이 큰 도움이 될 것이다. Graph Fourier Transform(푸리에 변환, Convolution 이론), Laplacian, Chebyshev Polynomial, Layer-wise Linear Model 등 GCN을 이해하기 위한 전반적인 흐름을 다 정리해두었다.)

 

 

이제 CNN(Convolutional Neural Network)에서 어떤 특징을 취했는지 소개해보겠다.

Convolution을 수행할 때는 Filter(또는 kernel)가 image를 순회하며 연산을 수행한다. 이 과정이 Weight Sharing으로 파라미터를 공유하게 되고, 파라미터 수가 작아져 오버피팅도 피할 수 있게 된다. 또한 Filter를 사용하여 Local feature도 잘 뽑아낼 수 있으며, down-sampling 효과도 얻을 수 있다.

하지만, CNN 구조를 그래프에 바로 적용할 수는 없다. 그래프 데이터에서 각 노드마다 이웃하는 노드의 개수가 다르고, 그래프 노드들의 순서가 바뀌었을 때 output이 일정하게 유지되지 않기 때문이다.

정리하자면, GCN이 CNN에서 취한 특징들은 다음과 같다.

• Weight Sharing (파라미터 감소)
• Local Connectivity (Convolutional Filter 역할)
• Use of Multi-layer (이웃노드~간접적으로 연결된 노드의 영향까지)

 

 

GCN

GCN의 특징은 다음과 같다.

(1) 그래프 input = f(X,A)

여기서 X는 Node feature이고, A는 Adjacency matrix를 의미한다. 그래프이기에 모델 구축을 위해서는 X와 A가 모두 필요하다.

 

GCN의 Hidden state는 아래와 같은 식을 통해 업데이트된다.

GCN Hidden State 업데이트 과정

 

GCN Forward Model for Semi-Supervised Node Classification

 

Training 과정에서 loss는 다음과 같다. 모든 labelled 데이터에 대해서 학습하고, unlabelled 데이터에 대해 inference하는 구조이다.

Cross-entropy error over all labelled data

 

 

(2) 그래프 노드들의 순서가 바뀌었을 때도 output이 일정하게 유지되는 Permutation invariance를 지킬 수 있는 함수여야 한다. 아래 그림에서 같은 그래프 구조지만 다른 위치를 가짐으로 인접행렬이 달라지게 된다. 이러한 오류를 방지하기 위한 방법이 Permutation invariance 또는 Readout이라고 한다. 

(Permutation은 그래프 구조를 의미하고, Invariance는 관계없이를 의미한다고 한다.)

예를 들어, graph classification에서는 I번째 node feature matrix에 대해 MLP를 적용하고 activation function을 적용했을 때 노드들 전체 합을 같은 값이 나오도록 readout으로 설정한다.

출처: https://github.com/heartcored98/Standalone-DeepLearning

 

(3) Semi-supervised learning

labelled data로 학습하고 unlabelled data로 inference한다. 따라서, labelled data를 idx_train으로, unlabelled data를 idx_test로 설정해주어야 한다.

 

 

마지막으로 전체적인 GCN 구조를 보고 끝맺도록 하겠다.

 

GCN 구조

 

 

Reference

1. https://signing.tistory.com/125

2. https://process-mining.tistory.com/176