[논문 리뷰 스터디] Semi-Supervised Classification with Graph Convolutional Networks

작성자: 15기 이승은

 

1. CNN

two great ideas of CNN - shared weights (filter size), translation invariance (이미지 위치 정보 사라짐)

 

2. Basics of GCN

• graph convolution을 이용하여 그래프에 포함된 node나 그래프 자체를 벡터 형태의 데이터로 변환 (기본적인 GCN에서는 node의 feature만을 고려 → edge feature가 존재하는 그래프는 다루지 X)
• Definition of Graph

G=(A,X), where A∈R^(N×N) represents an Adjacency matrix (node의 연결을 나타내는 인접 행렬 and X∈R^(N×d) represents a node feature matrix Here, N: 그래프에 포함된 node의 수, and d: node feature vector의 차원 (node feature의 수)

→ 그래프를 정의하기 위해서는 인접행렬 (노드 간 연결 관계에 관련된 행렬) 및 노드의 feature vector 값이 필요하다

• graph convolution

graph convolution (ψ)

H = ψ(A,X) = σ(AXW)

H∈R^(N×m), latent node feature matrix

• 여기서 W∈R^(d×m)는 learnable weight matrix이고 W를 찾는 것이 GCN을 학습시키는 것
• σ: non-linear activation function (e.g. Sigmoid, ReLU)

• Step 1) Find A, i.e. Adjacency Matrix
• Step 2) Find ‘node feature matrix X’ and ‘weight matrix W’
• Step 3) Calculate AXW

→ 이러한 방식으로 graph convolution ψ(A,X)=σ(AXW)를 통해 그래프에 존재하는 모든 node에 대한 m차원 latent feature matrix를 생

 

3. BUT 인접행렬의 한계

• 인접행렬에는 neighbor node와의 연결만 표현되어 있기 때문에 해당 node 자체 (자기 자신)에 대한 정보는 latent feature vector를 만들 때 고려 x
• 일반적으로 normalization이 되어 있지 않기 때문에 행렬곱을 했을 때 불안정한 결과가 나올 수 있음

→ 두 가지 문제점을 해결하기 위해

(1) A에 self-loop를 추가

(Self-loop가 추가된 인접 행렬 A’ = A + I; Here, I stands for an identity matrix)

(2) A를 정규화

 

4. 정리

• readout은 graph convolution layer를 통해 생성된 latent feature matrix를 그래프 전체를 표현하는 하나의 벡터로 변환하는 함수
• 일반적으로 readout은 전체 node의 latent feature vector를 평균내어 그래프 전체를 표현하는 하나의 벡터를 생성
• Graph classification/regression에서는 readout이 필수적이지만, node classification이나 link prediction에서는 readout이 없는 구조를 이용
• graph convolution layer를 거친 그래프 형태의 데이터는 기존의 머신러닝 알고리즘을 그대로 적용할 수 있게 변환됨

 

* GCN은 E (edge feature matrix)를 무시함 → GAT도 E 무시, MPNN은 E 고려

 

 

5. code implementation 

 

ref.

https://littlefoxdiary.tistory.com/m/17,

https://untitledtblog.tistory.com/152,

https://stellargraph.readthedocs.io/en/stable/demos/node-classification/gcn-node-classificatitn.html,

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