IQ Lab
← all posts
AI 2026.04.28 · 10 min read Advanced

GNN은 왜 깊이 쌓을수록 나빠지는가

GCN의 over-smoothing이 수학적 필연인 이유부터 APPNP의 closed-form 해결까지, 노드 표현이 붕괴하는 메커니즘을 스펙트럼 관점에서 추적한다.

📚 Gnn Deep Dive 5 / 6
  1. 01 그래프를 행렬로 보는 순간 GNN이 보인다
  2. 02 GCN은 어디서 왔는가 — Spectral 이론에서 한 줄 식까지
  3. 03 GNN 아키텍처들은 같은 문법으로 쓰여 있다
  4. 04 GNN은 어디까지 그래프를 구분할 수 있는가
  5. 05 GNN은 왜 깊이 쌓을수록 나빠지는가
  6. 07 GNN은 어디까지 확장될 수 있는가

ResNet은 152층을 쌓아 성능을 올린다. GCN은 4층만 넘어도 성능이 떨어진다. 같은 딥러닝인데 왜 이렇게 다른가? 그리고 이것이 구현 버그가 아니라 수학적 필연이라면, 어떻게 우회할 수 있는가?

현상: 노드가 모두 같아진다

GCN의 propagation은 다음과 같다.

H(l+1)=σ(A^H(l)W(l))H^{(l+1)} = \sigma(\hat{A} H^{(l)} W^{(l)})

A^=D~−1/2A~D~−1/2\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}는 self-loop을 포함한 정규화된 인접행렬이다. 이 연산의 본질은 각 노드가 이웃의 가중 평균을 취하는 smoothing이다.

한 층이면 이웃과 비슷해지고, 두 층이면 이웃의 이웃과 비슷해진다. 층이 깊어질수록 평균을 취하는 반경이 넓어진다. 그래프의 지름(diameter)이 O(log⁡n)O(\log n)인 경우, 몇 층 만에 모든 노드가 그래프 전체의 평균 정보를 보게 된다. 결국 모든 노드의 표현이 같은 방향으로 수렴한다.

lim⁡L→∞hi(L)=lim⁡L→∞hj(L)∀i,j∈V\lim_{L \to \infty} h_i^{(L)} = \lim_{L \to \infty} h_j^{(L)} \quad \forall i, j \in V

이를 over-smoothing이라 한다. Li et al. (2018)의 실증 데이터는 단조적이다.

LayerCoraCiteseerPubmed
281.5%70.3%79.0%
479.0%68.0%77.0%
871.0%60.0%70.0%
1650.0%38.0%55.0%

Layer 16에서 Cora 정확도 50%는 7-class 문제의 random guess(~14%)보다는 높지만, 모델이 거의 아무것도 학습하지 못했다는 뜻이다.

왜 필연인가: 스펙트럼 분석

over-smoothing은 구현 실수가 아니다. A^\hat{A}의 거듭제곱이 수렴하는 방향이 고정되어 있기 때문이다.

정리 1 · GCN의 Power Iteration 수렴

P=D~−1/2A~D~−1/2P = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}의 스펙트럼 분해를 P=UΛUTP = U\Lambda U^T라 하면,

lim⁡L→∞PLH=v1v1TH\lim_{L \to \infty} P^L H = v_1 v_1^T H

여기서 v1=d~/∥d~∥v_1 = \sqrt{\tilde{d}} / \|\sqrt{\tilde{d}}\|는 최대 고유값 1에 대응하는 고유벡터이다.

▷ 증명

PP의 고유값을 1=μ1>∣μ2∣≥⋯≥∣μn∣1 = \mu_1 > |\mu_2| \geq \cdots \geq |\mu_n|으로 정렬하면,

PL=∑kμkLvkvkT=v1v1T+∑k≥2μkLvkvkTP^L = \sum_k \mu_k^L v_k v_k^T = v_1 v_1^T + \sum_{k \geq 2} \mu_k^L v_k v_k^T

k≥2k \geq 2에서 ∣μk∣<1|\mu_k| < 1이므로 μkL→0\mu_k^L \to 0. 따라서 PL→v1v1TP^L \to v_1 v_1^T (rank-1). self-loop 추가(A~\tilde{A})로 PP가 bipartite structure를 갖지 않으므로 ∣μn∣<1|\mu_n| < 1도 보장된다. □\square

∎

수렴 속도는 spectral gap이 결정한다.

∥PLH−v1v1TH∥F≤∣μ2∣L⋅∥H∥F\|P^L H - v_1 v_1^T H\|_F \leq |\mu_2|^L \cdot \|H\|_F

∣μ2∣|\mu_2|가 1에 가까울수록(예: path graph) 느리게 붕괴하고, 0에 가까울수록(예: complete graph) 한 층 만에 붕괴한다. 완전 연결 그래프 KnK_n에서 over-smoothing은 단 1층 만에 완성된다.

임시 방편들: DropEdge와 PairNorm

over-smoothing을 완화하는 표면적 방법들이 있다.

DropEdge (Rong 2020)는 매 학습 step마다 edge를 랜덤하게 제거한다. Propagation matrix PP가 매번 달라지면 단일 dominant eigenvector로의 결정론적 수렴이 방해된다. PairNorm (Zhao 2020)은 각 층 출력의 pairwise distance 평균을 일정하게 유지한다. centering과 rescaling으로 Dirichlet energy E(H)=tr(HTLH)E(H) = \text{tr}(H^T L H)에 하한을 준다.

실증 결과는 인상적이다. Cora 16층에서 vanilla GCN 50% → DropEdge 65% → PairNorm 73.5%. 하지만 이들은 근본을 고치지 않는다.

⚠ 트레이드오프

DropEdge와 PairNorm은 PL→v1v1TP^L \to v_1 v_1^T라는 동역학 자체를 바꾸지 않는다. 노이즈와 정규화로 붕괴 속도를 늦출 뿐이다. 뮤추얼 인포메이션 I(X;H(L))I(X; H^{(L)})는 여전히 층이 깊어질수록 감소한다. GraphSAGE의 neighbor sampling도 마찬가지다 — expected dynamics는 vanilla GCN과 같고, variance만 커진다. 16층 이상에서는 이 방법들 모두 한계에 부딪힌다.

본질적 해결: APPNP

APPNP (Klicpera 2019)는 propagation과 prediction을 분리한다.

먼저 MLP로 초기 예측을 만든다: H(0)=fθ(X)H^{(0)} = f_\theta(X). 그다음 personalized PageRank 방식으로 propagate한다.

Z∗=α(I−(1−α)P~)−1H(0)=α∑k=0∞(1−α)kP~kH(0)Z^* = \alpha (I - (1 - \alpha) \tilde{P})^{-1} H^{(0)} = \alpha \sum_{k=0}^{\infty} (1-\alpha)^k \tilde{P}^k H^{(0)}

α\alpha는 teleport probability다. 매 hop마다 확률 α\alpha로 초기 표현 H(0)H^{(0)}으로 리셋된다. 이 구조의 spectral filter는 다음과 같다.

g^APPNP(μk)=α1−(1−α)μk\hat{g}_{\text{APPNP}}(\mu_k) = \frac{\alpha}{1 - (1-\alpha)\mu_k}

μ1=1\mu_1 = 1에서 g^=1\hat{g} = 1, μk<1\mu_k < 1에서도 g^>0\hat{g} > 0이다. 모든 spectral component가 살아남는다. vanilla GCN에서 μkL→0\mu_k^L \to 0(k≥2k \geq 2)으로 사라졌던 고주파 성분들이 보존된다. K→∞K \to \infty에서도 rank-1 붕괴가 없다.

실용적으로는 K=10K = 10번 power iteration으로 충분하다. K=10K = 10의 오차는 closed-form 대비 10−410^{-4} 이하다.

Jumping Knowledge Network (JKN, Xu 2018)는 다른 접근이다. 모든 층의 출력을 최종 표현에 결합한다.

hvJK=concat(hv(1),hv(2),…,hv(L))h_v^{\text{JK}} = \text{concat}(h_v^{(1)}, h_v^{(2)}, \ldots, h_v^{(L)})

깊은 층이 붕괴해도 얕은 층의 정보가 보존된다. concat 외에 max-pool, LSTM-aggregate 변종도 있다.

정리

  • Over-smoothing은 버그가 아니다. PL→v1v1TP^L \to v_1 v_1^T라는 spectral 필연이다.
  • 수렴 속도는 spectral gap 1−∣μ2∣1 - |\mu_2|에 의해 결정된다. dense graph일수록 빠르게 붕괴한다.
  • DropEdge, PairNorm, neighbor sampling은 붕괴를 늦추지만 막지 못한다. 16층 이상에서 한계가 온다.
  • APPNP는 모든 hop의 정보를 기하급수 가중합으로 보존한다 — 이론적으로 무한 층도 가능하다.
  • JKN은 all-layer concat으로 계층적 정보를 보존한다.
  • heterophilic graph에서는 APPNP의 low-pass bias가 오히려 해가 된다. learnable polynomial filter(GPR-GNN)가 필요하다.

GNN의 깊이 문제는 결국 하나의 질문으로 수렴한다 — propagation이 어떤 spectral shape을 만드는가. 이 질문에 정직하게 답한 것이 APPNP이고, 그 일반화가 현대 spectral GNN 연구의 주류다.

REF
REF
# gnn # over-smoothing # graph-laplacian # appnp # jumping-knowledge