[Paper Review] SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

3 분 소요

이 포스팅은 SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS 논문을 읽고 정리한 글입니다.

Introduction

그래프 데이터는 노드 간의 복잡한 관계를 내재하고 있어, 소셜 네트워크 분석·지식 그래프·분자 구조 예측 등 다양한 태스크에서 폭넓게 활용됩니다.
이 논문에서는 그래프 컨볼루션 네트워크(GCN) 를 제안하여, 그래프 상에 일부 노드 레이블만 주어졌을 때에도 효과적으로 반지도(node-level) 분류를 수행하는 방법을 소개합니다.

문제 설정
- 그래프 $G=(V,E)$, 노드 특성 행렬 $X\in\mathbb{R}^{N\times C}$, 레이블된 노드 집합 $\mathcal{Y}_L\subset V$
- 목표: $\mathcal{Y}_L$ 외의 모든 노드에 대해 클래스 확률 예측
핵심 아이디어
1. 그래프 신호 처리 관점에서 저주파 필터만을 남기는 컨볼루션 연산
2. 라플라시안 다항식 근사를 통해 효율적이고 희소한 행렬곱 형태로 구현

Graph & Fourier Transform

Fourier Transform
- Signal을 주파수 성분(저주파·고주파)으로 분해
- Fourier basis에 투영하여, 각 주파수 성분의 포함 정도를 파악
  
  어떤 주파수가 Signal에 얼마나 포함되어 있는지 알 수 있다.
Graph Fourier Transform(GFT)
- 노드의 Feature 벡터를 신호로 간주
- 그래프 라플라시안 고유분해를 통해 “주파수”(고유값)를 정의
- Frequency를 Feature들 간의 차이라고 정의한다.
- 고주파 성분일수록 인접 노드 간 값 변화가 크다는 의미
어떤 형태의 그래프가 Signal에 어느 정도 포함되어 있는지 알 수 있다.

</br>

저주파(작은 고유값) 성분은 인접 노드 간 차이가 작아 유사한 정보를 담고 있다.
이 저주파 정보만 필터링한 뒤 역변환하면,
인접 노드 간 스무딩(컨볼루션) 연산이 수행된다.

Background

1. Graph Laplacian & GFT

$L = I - D^{-1/2} A\,D^{-1/2}$$L = U\,\Lambda\,U^\top,\quad \Lambda = \mathrm{diag}(\lambda_1,\dots,\lambda_N)$

$U$: 라플라시안 고유벡터(그래프 푸리에 기저)
$\Lambda$: 고유값(주파수) 대각행렬

GFT(분해):
$\hat x = U^\top x$
IGFT(역변환):
$x = U\,\hat x = \sum_{i=1}^N \hat x_i\,u_i$

2. Spectral Filter as a Function of $L$

그래프 컨볼루션은 스펙트럼 도메인 필터 $g(\lambda)$를 적용한 후 역변환한 결과로,
$y = U\,g(\Lambda)\,U^\top x = g(L)\,x.$

Identity+Laplacian 예시: $g(\lambda)=1+\lambda$ 이면
$g(L)x = (I + L)\,x = x + (I - D^{-1/2}AD^{-1/2})\,x.$
다항식 필터:
$g(L)x = \sum_{k=0}^K \theta_k\,L^k\,x,$
$k$번 곱할수록 $k$-이웃까지의 정보를를 Aggregation.

3. Chebyshev Polynomial Approximation

근사식:
$g(L)x \approx \sum_{k=0}^K \theta_k\,T_k(\tilde L), \quad \tilde L = \frac{2}{\lambda_{\max}}L - I.$
1차 근사 (K=1):
$g(L)x \approx \theta_0\,x + \theta_1\,(L + I)\,x.$

4. First-order Simplification & Renormalization

1차 필터: $g(L)\approx\theta_0 I + \theta_1 L$
Renormalization:
$L + I = \tilde D^{-1/2}\,\tilde A\,\tilde D^{-1/2},\quad \tilde A = A + I.$
GCN 전파 규칙:
$H^{(l+1)} = \sigma\bigl(\tilde D^{-1/2}\tilde A\,\tilde D^{-1/2}H^{(l)}W^{(l)}\bigr).$

GCN Model

Layer-wise Propagation Rule

각 레이어 $l$에서 입력 $H^{(l)}$에 대해
$H^{(l+1)} = \sigma\bigl(\underbrace{\tilde D^{-1/2}\,\tilde A\,\tilde D^{-1/2}}_{\text{스무딩 필터}} \;H^{(l)}\,W^{(l)}\bigr),$

$H^{(0)} = X$ (입력 노드 특성 행렬)
$W^{(l)}\in\mathbb{R}^{D_l\times D_{l+1}}$: 학습 가능한 선형 변환 파라미터
$\sigma$: ReLU 등 비선형 활성화 (보통 각 레이어 뒤에 적용)
Self-loop 및 대칭 정규화로 “자기 메시지 포함 + 이웃 스무딩” 효과

Semi-supervised Learning & Training Procedure

Forward Pass
- 입력 $X$ → 여러 GCN 레이어 순차 적용 → $H^{(L)}$
- 최종 레이어 출력에 softmax 적용:
  $Z = \mathrm{softmax}\bigl(H^{(L)}\bigr)\in\mathbb{R}^{N\times F},$
  여기서 $Z_{i,f}$는 노드 $i$가 클래스 $f$일 확률

Loss Computation
- 레이블된 노드 집합 $\mathcal{Y}L$에 대해서만 교차 엔트로피 손실 계산:
  $\mathcal{L}_{\text{CE}} = -\sum_{i\in\mathcal{Y}_L}\sum_{f=1}^F Y_{if}\,\ln Z_{if},$
  $Y{if}$는 원-핫 인코딩된 진짜 레이블

Regularization
- L2 Weight Decay: 모든 $W^{(l)}$에 대해
  $\mathcal{L}{\text{reg}} = \frac{\lambda}{2}\sum{l}|W^{(l)}|^2_F$ 추가
- Dropout: 각 GCN 레이어 입력 또는 출력 텐서에 확률 $p$로 적용
  (보통 $p=0.5$를 첫/마지막 레이어에 사용)

Optimizer & Hyperparameters
- Adam (learning rate $\alpha=0.01$, $\beta_1=0.9$, $\beta_2=0.999$)
- 배치 크기: 전체 그래프 기반 GCN은 Full-batch 학습
  (작은 그래프: $N$ 노드 전체로 학습, 큰 그래프는 미니배치 기법 권장)
- Epoch 수: 보통 200~300 epoch, 성능 Plateau 시 Early Stopping
- Early Stopping: 검증 집합 정확도 기준 10‒20 epochs patience

Training Loop (Pseudo-code)

for epoch in range(max_epochs):
    model.train()
    optimizer.zero_grad()
    Z = model(A_norm, X)               # forward pass
    loss_ce = cross_entropy(Z[train_idx], Y[train_idx])
    loss_reg = weight_decay * sum(norm(W) for W in model.weights)
    loss = loss_ce + loss_reg
    loss.backward()
    optimizer.step()
       
    # validation
    model.eval()
    Z_val = model(A_norm, X)
    val_acc = accuracy(Z_val[val_idx], Y[val_idx])
    if val_acc > best_val_acc:
        best_val_acc = val_acc
        patience_counter = 0
        save_model(model)
    else:
        patience_counter += 1
        if patience_counter >= patience_limit:
            break

Implementation

$\tilde A$와 $\tilde D$를 사전 계산
희소(sparse) 연산 활용
첫/마지막 레이어 드롭아웃(0.5), L2 정규화 적용
Adam 옵티마이저(학습률 0.01)

Experiments & Results

데이터셋: Cora, Citeseer, Pubmed
비교 대상: Laplacian Regularization, Planetoid, DeepWalk, ICA 등
성능 (Cora 예시)

모델	정확도 (%)
Planetoid*	75.7
GCN (ours)	81.5

학습 속도: 전체 엣지 개수에 선형 스케일, Planetoid 대비 3~5배 빠름

Conclusion

이 논문은 그래프 신호 처리 관점에서 GCN의 핵심 아이디어를 제시하고, 이를 반지도 노드 분류에 효과적으로 적용한 첫 사례입니다.

주요 기여
1. 스펙트럼 필터링 프레임워크
  - 그래프 푸리에 변환 기반 저주파 필터링을 $g(L)$ 다항식 형태로 근사
  - 단순하면서도 강력한 1차 근사 GCN 계층 설계
2. 효율성과 성능
  - 희소 행렬곱만으로 구현 가능해 대규모 그래프에도 선형적 확장성 확보
  - Cora/Citeseer/Pubmed 등에서 기존 최첨단 대비 3–5%p 높은 정확도 달성

Reference

X Facebook LinkedIn Bluesky

Junhee Kim