Semi-Supervised Classification with Graph Convolutional Networks
그래프 합성곱 네트워크를 이용한 준지도 분류
Thomas N. Kipf, Max Welling (2016)
스펙트럴 그래프 이론에 기반한 그래프 컨볼루션을 1차 근사로 단순화하여, 각 노드가 1-홉 이웃의 특징을 집계하는 효율적인 레이어별 전파 규칙을 도출한 준지도 노드 분류 모델이다.
배경
CNN이 이미지에서, RNN이 시퀀스 데이터에서 큰 성공을 거두었지만, 소셜 네트워크, 인용 네트워크, 분자 구조 등 그래프 구조 데이터에 딥러닝을 적용하는 것은 여전히 어려웠다. 기존 스펙트럴 그래프 컨볼루션은 고유값 분해의 높은 연산 비용과 공간적 국소성 부족 등의 문제가 있었다. 준지도 학습(semi-supervised learning) 설정에서 소수의 레이블만으로 그래프의 모든 노드를 분류하는 것이 실용적으로 중요한 과제였다.
핵심 아이디어
GCN은 스펙트럴 그래프 컨볼루션에 체비셰프 다항식의 1차 근사를 적용하여, 각 레이어에서 노드가 자신과 직접 연결된 이웃의 특징을 가중 평균하는 단순한 전파 규칙을 도출한다. 전파 규칙은 H^(l+1) = σ(D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l))로, 여기서 Ã는 자기 연결을 추가한 인접 행렬, D̃는 차수 행렬이다. 자기 연결(self-loop) 추가로 자신의 특징도 보존하면서, 정규화된 인접 행렬로 이웃 특징을 집계한다. 이 단순한 규칙을 여러 층 쌓으면 다중 홉 이웃의 정보까지 전파할 수 있다.
방법론
입력 특징에 2-3개의 GCN 레이어를 적용하고, 최종 레이어에서 소프트맥스로 노드 분류를 수행한다. 전체 그래프의 인접 행렬을 사용한 풀배치(full-batch) 학습을 수행하며, 소수의 레이블 노드에 대한 크로스엔트로피 손실만으로 학습한다. 드롭아웃을 적용하여 과적합을 방지한다.
주요 결과
Cora, Citeseer, Pubmed 인용 네트워크와 NELL 지식 그래프에서 기존 준지도 학습 방법(Label Propagation, DeepWalk, Planetoid 등)을 크게 상회했다. 적은 수의 레이블(클래스당 20개)만으로도 높은 분류 정확도를 달성했으며, 학습 속도도 매우 빨랐다.
임팩트
GCN은 그래프 뉴럴 네트워크(GNN) 분야를 사실상 개척한 논문으로, 수천 편의 후속 연구에 영향을 미쳤다. 메시지 패싱(message passing)이라는 GNN의 핵심 프레임워크를 확립했으며, GAT, GraphSAGE 등 수많은 변형 모델의 기반이 되었다. 소셜 네트워크 분석, 추천 시스템, 약물 발견, 교통 예측 등 다양한 실세계 응용에서 그래프 기반 딥러닝의 표준 빌딩 블록이 되었다.