GNN은 그래프에서 무엇을 학습하는가

노드 분류부터 그래프 생성까지, GNN 응용 태스크 전반을 관통하는 설계 원칙과 표현력의 한계를 추적한다.

GNN은 노드를 분류하고, 그래프를 분류하고, 링크를 예측하고, 새 그래프를 생성한다. 네 가지 태스크는 겉보기에 달라 보이지만, 속을 들여다보면 하나의 질문이 반복된다. “그래프 구조에서 어떤 정보를 어떻게 읽어낼 것인가?” — 그리고 그 답을 어떤 식으로 손실 없이 출력으로 변환할 것인가.

노드 분류 — 이웃 정보가 레이블을 만든다

노드 분류의 기본 설정은 단순하다. 일부 노드에만 레이블이 있고, 나머지는 없다. GNN은 레이블 없는 노드의 레이블을 예측해야 한다. 손실 함수는 레이블 있는 노드에만 적용된다.

\mathcal{L} = -\sum_{v \in V_L} \sum_c y_{vc} \log \hat{y}_{vc}

흥미로운 점은 레이블 없는 노드가 손실에 기여하지 않으면서도 메시지 패싱에는 참여한다는 것이다. 이들은 중간 노드 역할을 하며 레이블 있는 노드의 신호를 이웃으로 전파한다. Cora 데이터셋에서 MLP가 55%, GCN이 81.5%를 기록하는 이유가 여기 있다. 26%p 차이는 피처만으로는 얻을 수 없는 구조 정보의 기여다.

GAT(83.0%), APPNP(83.3%), GCNII(85.5%)로 올라가는 성능 향상의 공통 방향은 레이블 신호를 더 멀리, 더 안정적으로 전파하는 것이다. APPNP는 Personalized PageRank로 propagation 범위를 확장하고, GCNII는 residual connection으로 깊은 층에서도 over-smoothing을 억제한다.

✎ 트레이드오프 — Transductive vs Inductive

Cora 표준 설정(transductive)은 테스트 노드도 학습 시 그래프에 포함된다. OGB-Arxiv 같은 inductive 설정에서는 학습 시 보지 못한 새 노드를 예측해야 한다. GAT와 GraphSAGE가 inductive 환경에서 상대적으로 강한 이유는 attention과 샘플링 기반 집계가 그래프에 독립적인 파라미터를 학습하기 때문이다.

그래프 분류 — READOUT이 표현력을 결정한다

노드 분류가 하나의 그래프 위에서 작동한다면, 그래프 분류는 여러 그래프 인스턴스 각각에 레이블을 부여한다. 핵심 문제는 가변 크기의 노드 집합을 고정 크기 벡터로 압축하는 READOUT이다.

h_G = \text{READOUT}(\{h_v : v \in V\})

READOUT 선택은 단순한 구현 결정이 아니다. sum은 multiset-injective다 — 같은 원소 구성이라도 개수가 다르면 다른 출력을 낸다. mean은 크기 정보를 잃고, max는 단일 최댓값만 남긴다. Xu et al.(2019)의 이론적 분석은 GIN + sum readout이 1-WL 표현력의 상한에 도달함을 증명한다. MUTAG 벤치마크에서 GIN(89.4%) > Mean readout(86.5%) > Max readout(84.2%)의 순서는 이 이론을 실증적으로 뒷받침한다.

분자 분류에서 Graphormer(80.5 ROC-AUC)가 GIN(75.8)을 크게 앞서는 것은 1-WL 표현력의 실용적 한계를 보여준다. 벤젠 환, 작용기 같은 부분구조 카운팅은 1-WL이 처리하지 못하는 영역이다. PNA(79.0)가 sum, mean, max, std를 모두 concat해 degree 스케일링을 적용하는 이유가 여기 있다 — 같은 표현력 상한 내에서 더 많은 신호를 추출하는 전략이다.

링크 예측 — 인코더와 디코더의 분리

링크 예측은 두 노드 사이의 관계 유무를 예측한다. 구조는 GNN 인코더로 노드 임베딩을 학습하고, 디코더로 쌍별 점수를 계산하는 2단계다.

디코더 선택은 예측하려는 관계의 성격에 달려 있다. 내적 디코더( $s_{uv} = h_u^T h_v$ )는 대칭이라 방향성 없는 관계에만 적합하다. 지식 그래프의 parent_of처럼 비대칭 관계는 ComplEx나 RotatE가 필요하다.

디코더	대칭	역관계	합성관계
DistMult	✓	✗	부분
ComplEx	✗	✓	부분
RotatE	✗	✓	✓

FB15k-237에서 RotatE(MRR 0.34)가 DistMult(0.29)를 앞서는 격차는 parent_of → child_of 같은 역관계와 grandparent = parent ∘ parent 같은 합성관계를 표현할 수 있느냐 없느냐의 차이다. CompGCN이 GNN 인코더와 ComplEx 디코더를 결합해 MRR 0.37을 달성하는 것은, 구조 정보를 담은 노드 임베딩이 디코더의 기반 품질을 높인다는 것을 보여준다.

그래프 생성 — 순열 불변성이 핵심 난관이다

그래프 생성은 앞선 세 태스크와 다른 차원의 문제를 안고 있다. $n$ 개 노드의 그래프에는 $n!$ 개의 동등한 인접 행렬 표현이 존재한다. 생성 모델이 이 중 “어느 것”을 출력해야 하는가?

GraphVAE는 병렬로 인접 행렬 전체를 생성하고 Hungarian algorithm으로 순열을 맞춘다( $O(n^3)$ ). 그래서 소규모 그래프( $n \leq 40$ )에서만 실용적이다. GraphRNN은 BFS 순서로 노드를 하나씩 추가해 순열 공간을 줄인다. GCPN은 부분 분자 위에서 강화학습 에이전트가 원자와 결합을 추가하며 QED, 합성 가능성 같은 화학 보상을 최적화한다.

DiGress(Vignac 2022)의 이산 확산 모델은 다른 접근을 취한다. 그래프를 점진적으로 노이즈화하고 역방향으로 복원하는 과정에서, equivariant 네트워크 설계로 순열 불변성을 구조 안에 내장한다.

⚠ 트레이드오프 — 표현력 vs 계산 비용

DiGress는 MUTAG validity 99%, FCD 3.1로 GraphVAE(validity 72%, FCD 25.1)와 GraphRNN(FCD 8.7)을 압도한다. 그러나 수십~수백 개의 denoising step이 필요하고 $n > 100$ 노드에서 메모리가 폭발한다. GraphRNN은 느리지만 100+ 노드도 처리 가능하다. 약물 발견처럼 품질이 최우선인 곳에는 확산 모델, 빠른 탐색이 필요한 곳에는 GraphRNN이 현실적 선택이다.

정리

네 태스크를 가로지르는 공통 원칙이 있다.

표현력은 항상 구조에서 온다. MLP 대비 GCN의 26%p, Sum 대비 Mean readout의 3%p, GNN 인코더가 결합된 CompGCN의 MRR 향상 — 모두 그래프 구조 정보의 기여다.
READOUT과 디코더 선택은 이론적으로 분석 가능하다. Sum의 multiset-injectivity, RotatE의 관계 패턴 표현 능력은 실험 전에 이론으로 예측된다.
순열 불변성은 해결됐지만 비용이 다르다. BFS 순서(GraphRNN), 매칭(GraphVAE), 등변 설계(DiGress) — 각각 다른 계산 비용과 표현력을 교환한다.
1-WL 표현력은 이론적 상한이지 실용적 상한이 아니다. 화학 부분구조, 장거리 의존성에는 positional encoding, attention, 또는 고차 WL이 필요하다.

다음 글에서는 이 표현력 한계를 정면으로 다루는 현대 그래프 트랜스포머 — Graphormer의 공간 인코딩과 중심성 인코딩 설계를 추적한다.