[OUTTA Alpha팀 논문 리뷰 요약] Part 4-3. GCN (Graph Convolutional Networks)

논문 링크: https://arxiv.org/abs/1609.02907

Semi-Supervised Classification with Graph Convolutional Networks

 
유튜브 설명 링크: https://youtu.be/yY-DpulpUwk?si=vVFxBzoyv-j_KIxS

---

1. Introduction

• 그래프 기반 반지도학습 배경
  • 일부 노드만 라벨이 있는 상황에서, 전체 노드를 분류(또는 회귀)하는 문제
  • 기존 방법: 라플라스 정규화(Laplacian regularization) 기반으로, 인접 노드 사이 라벨이 유사하다는 가정
  • 하지만 엣지 자체가 “유사성” 외 다른 의미를 담을 수도 있어 한계

$$\mathcal{L}=\mathcal{L}_ {0} + \lambda\mathcal{L}_ {reg}, \mathcal{L}_ {reg} = \sum_ {i.j}A_{ij}||f(X_i)-f(X_j)||^2=f(X)^{T}\Delta f(X)\tag{1}$$

• 본 논문 기여
  1. 그래프 구조를 직접 학습하는 인공신경망 모델 $f(X,A)$ 제안
  2. 네트워크의 학습을 통해, 라벨 정보가 있는 소수 노드로부터 gradient를 전체 그래프에 전파 가능
  3. Spectral Graph Convolution의 1차 근사 기법으로 간소화된 GCN 레이어 설계

---

2. Fast Approximate Convolutions on Graphs

1. Spectral Graph Convolution $$g_\theta * x = U\,g_\theta\,U^T x$$
   • $U$: 그래프 라플라시안의 고유벡터, $g_\theta$​: 주파수영역 필터
2. Chebyshev 다항식 근사 $$g_\theta' * x = \sum_{k=0}^{K} \theta'_k \, T_k(\tilde{L}) \, x$$
   • $T_k$​: Chebyshev 다항식, $\tilde{L}$은 정규화된 라플라시안
3. 1차 근사 & 간소화 $$g_\theta' * x \approx \theta'_0 \, x \;+\; \theta'_1 (L - I_N)\, x = \theta'_0 \, x - \theta'_1 D^{-\frac12} A \, D^{-\frac12} x$$
   • 파라미터가 $\theta_0, \theta_1$​ 두 개로 단순화
4. Renormalization Trick
   • $\tilde{A} = A + I_N,\quad \tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$​
   • $\tilde{D}^{-\frac12}\,\tilde{A}\,\tilde{D}^{-\frac12}$​ 형태로 다시 정규화
   • Vanishing/Exploding 방지 및 수치적 안정성 확보

• 최종 GCN 레이어:$$H^{(l+1)} = \sigma\bigl(\tilde{D}^{-\frac12}\,\tilde{A}\,\tilde{D}^{-\frac12}\,H^{(l)}\,W^{(l)}\bigr)$$
  • $H^{(l)}$: $l$-번째 레이어 은닉 표현, $W^{(l)}$: 가중치
• 시간 복잡도:
  • Edge 수 $|E|$에 선형 $\rightarrow O(|E|\;F\;C)$ (Feature 차원 $C$에서 $F$개 필터 사용 시)

---

3. Semi-Supervised Node Classification

• 문제 설정: 일부 노드만 라벨이 있고, 그래프는 무방향 ($A$이 대칭)))
• 2-Layer GCN 예시 $$Z = f(X,A) = softmax\!\Bigl(\hat{A}\,\mathrm{ReLU}\bigl(\hat{A}\,X\,W^{(0)}\bigr)\,W^{(1)}\Bigr)$$
  • $\hat{A} = \tilde{D}^{-\frac12}\,\tilde{A}\,\tilde{D}^{-\frac12}$​
• Loss: Cross-Entropy for labeled nodes $$L = -\sum_{l \in \mathcal{Y}_L} \sum_{f=1}^{F} Y_{lf}\,\ln Z_{lf}$$​
  • $\mathcal{Y}_L$​: 라벨 있는 노드 집합

---

4. Related Work

• 그래프 기반 반지도학습:
  • 라플라시안 정규화 기반 [2-4]
  • 그래프 임베딩(예: skip-gram + random walk) 기반 [5-9]
• 그래프 신경망(GNN)
  • RNN/CNN 확장
  • 본 논문은 Chebyshev 근사 + Renormalization으로 간소화
  • 대형 그래프에 확장 용이 & 학습 효율 높음

---

5. Experiments

• 데이터셋: Citeseer, Cora, Pubmed (인용 네트워크) + NELL (지식 그래프)
• 비교대상:
  • 라플라시안 정규화 기반 모델 [2,3,4]
  • Skip-gram 임베딩 기반 모델 [6,9]
  • 점층분류(ICA) [10]
• 설정: Cora에서 하이퍼파라미터 튜닝 → 동일 세팅으로 Citeseer, Pubmed 실험

---

6. Results

• 정확도
  • GCN이 다양한 그래프 확산 기법 및 임베딩 기반 모델보다 상위 성능
  • ICA 대비도 우수 성능
  •  

    

• Forward 확산 기법 비교
  • GCN이 라플라시안 정규화 기반보다 효율적 + 성능 좋음

  • 

• 학습 속도
  • 무작위 생성 그래프에서도 GCN이 빠른 학습 시간 보여줌

  • 

---

7. Discussion

• 장점
  1. 고성능: 기존 라플라시안 정규화·skip-gram 임베딩 대비 성능 우수
  2. 간단 + 효율적: Chebyshev 1차 근사 + Renormalization Trick 도입 → ∣E∣|E|∣E∣에 선형 스케일
  3. 다양한 그래프(인용 네트워크, 지식 그래프 등)에 적용 가능
• 한계
  1. 무방향 그래프에만 직접 적용 (방향 그래프나 동적 그래프는 추가적 처리 필요)
  2. Locality 가정(1-hop 이웃) & 자기자신 연결(Identity) 활용 → 데이터셋에 따라 보완 필요
  3. 대규모 그래프에서 여전히 메모리 사용량이 문제될 수 있음 (그러나 하드웨어 발전으로 일부 해소 가능)