그래프 신경망 (Graph Neural Networks)¶

난이도: 중급~고급
선수 지식: 신경망 기초, 어텐션 메커니즘
관련 문서: Transformer | 차원 축소 | 앙상블 방법

개요¶

현실 세계의 많은 데이터는 그래프 (Graph) 구조를 가진다. 소셜 네트워크, 분자 구조, 지식 그래프, 추천 시스템의 사용자-아이템 관계 등이 대표적이다. 이러한 데이터에 기존 신경망을 직접 적용하기 어려운 이유는 세 가지이다:

가변적 이웃 수: 각 노드의 이웃 수가 다르므로 고정 크기 입력을 기대하는 CNN/MLP를 바로 쓸 수 없다
순열 불변성 (Permutation Invariance): 이웃 노드의 순서에 무관하게 같은 결과를 내야 한다
비유클리드 구조 (Non-Euclidean): 격자(grid) 위에 정의된 이미지와 달리, 그래프에는 고정된 공간 좌표가 없다

그래프 신경망(GNN)은 이러한 제약을 해결하는 딥러닝 모델군으로, 핵심 아이디어는 단순하다: 각 노드가 이웃의 정보를 반복적으로 모아(aggregate) 자신의 표현(representation)을 갱신한다.

GNN의 역사는 2005년 Gori et al.의 초기 연구에서 시작하여, 2017년 GCN (Kipf & Welling), 2018년 GAT (Velickovic et al.), 2019년 GIN (Xu et al.)으로 이어지며 빠르게 발전하였다.

핵심 개념¶

1. 그래프 표현¶

그래프 \(G = (V, E)\)는 노드 집합 \(V\)와 간선 집합 \(E\)로 구성된다.

인접 행렬 (Adjacency Matrix): \(A \in \{0, 1\}^{|V| \times |V|}\), \(A_{ij} = 1\)이면 노드 \(i\)와 \(j\) 사이에 간선이 존재
노드 특성 행렬 (Node Feature Matrix): \(X \in \mathbb{R}^{|V| \times d}\), 각 노드의 \(d\)차원 특성 벡터
차수 행렬 (Degree Matrix): \(D_{ii} = \sum_j A_{ij}\), 대각 행렬

2. 메시지 전달 프레임워크 (Message Passing)¶

Gilmer et al. (2017)이 제안한 메시지 전달 신경망(MPNN) 프레임워크는 대부분의 GNN을 통합하는 일반적 관점을 제공한다. 각 레이어에서 세 단계가 반복된다:

1단계 — 메시지 생성 (Message):

\[m_{ij}^{(l)} = \text{MSG}^{(l)}(h_i^{(l)}, h_j^{(l)}, e_{ij})\]

여기서 \(h_i^{(l)}\)은 레이어 \(l\)에서 노드 \(i\)의 은닉 표현, \(e_{ij}\)는 간선 특성이다.

2단계 — 집계 (Aggregate):

\[\tilde{h}_i^{(l)} = \text{AGG}^{(l)}\left(\{m_{ij}^{(l)} : j \in \mathcal{N}(i)\}\right)\]

여기서 \(\mathcal{N}(i)\)는 노드 \(i\)의 이웃 집합이다. AGG는 순열 불변 함수여야 한다 (sum, mean, max 등).

3단계 — 갱신 (Update):

\[h_i^{(l+1)} = \text{UPDATE}^{(l)}(h_i^{(l)}, \tilde{h}_i^{(l)})\]

graph LR
    subgraph "메시지 전달 1회 반복"
        A["이웃 노드들<br/>h_j"] -->|"MSG: 메시지 생성"| B["메시지 집합<br/>{m_ij}"]
        B -->|"AGG: 집계<br/>(sum/mean/max)"| C["집계된 표현<br/>h̃_i"]
        C -->|"UPDATE: 갱신"| D["새로운 노드 표현<br/>h_i^(l+1)"]
        E["현재 노드<br/>h_i"] -->|"결합"| C
    end

3. 이웃 집계와 수용 영역¶

\(k\)번의 메시지 전달을 거치면 각 노드는 \(k\)-홉(hop) 이웃의 정보를 반영한다. 이것이 GNN의 수용 영역 (Receptive Field)이다. CNN에서 커널 크기와 레이어 수가 수용 영역을 결정하는 것과 유사하다.

4. 세 가지 작업 수준¶

작업 수준	설명	출력	예시
노드 분류 (Node Classification)	각 노드의 레이블 예측	\(\hat{y}_i = f(h_i^{(L)})\)	소셜 네트워크에서 봇 탐지
간선 예측 (Link Prediction)	두 노드 사이 간선 존재 여부 예측	\(\hat{y}_{ij} = g(h_i^{(L)}, h_j^{(L)})\)	추천 시스템
그래프 분류 (Graph Classification)	전체 그래프의 레이블 예측	\(\hat{y}_G = h(\text{READOUT}(\{h_i^{(L)}\}))\)	분자 독성 예측

READOUT 함수는 모든 노드 표현을 하나의 그래프-수준 표현으로 요약한다. 단순 합/평균부터 계층적 풀링(hierarchical pooling)까지 다양한 방법이 있다.

상세 내용¶

GCN (Graph Convolutional Network)¶

Kipf & Welling (2017)이 제안한 GCN은 스펙트럴 그래프 이론(spectral graph theory)에서 출발하여 단순하고 효과적인 공간적(spatial) 형태로 근사한 모델이다.

스펙트럴 관점: 그래프 라플라시안 \(L = D - A\)의 고유 분해를 이용한 그래프 푸리에 변환에 기반한다. 그러나 고유 분해의 \(O(n^3)\) 비용과 그래프 의존성 문제가 있어, 체비셰프 다항식으로 근사한 뒤 1차 항까지만 취하면 다음의 공간적 형태가 된다.

최종 공식:

\[H^{(l+1)} = \sigma\left(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}H^{(l)}W^{(l)}\right)\]

여기서: - \(\hat{A} = A + I_N\): 자기 루프(self-loop)를 추가한 인접 행렬 - \(\hat{D}_{ii} = \sum_j \hat{A}_{ij}\): \(\hat{A}\)의 차수 행렬 - \(W^{(l)} \in \mathbb{R}^{d_l \times d_{l+1}}\): 학습 가능한 가중치 행렬 - \(\sigma\): 활성화 함수 (예: ReLU)

직관: \(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}\)는 대칭 정규화된 인접 행렬로, "자기 자신 포함 이웃의 특성을 차수에 비례하여 평균"하는 연산이다.

GAT (Graph Attention Network)¶

Velickovic et al. (2018)이 제안한 GAT는 모든 이웃을 동일하게 취급하는 GCN의 한계를 극복하기 위해 어텐션 계수를 도입한다.

어텐션 계수 계산:

\[e_{ij} = \text{LeakyReLU}\left(\vec{a}^T [Wh_i \| Wh_j]\right)\]

\[\alpha_{ij} = \text{softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \exp(e_{ik})}\]

여기서 \(\|\)는 벡터 연결(concatenation), \(\vec{a}\)는 학습 가능한 어텐션 벡터이다.

노드 갱신 (Multi-head Attention):

\[h_i' = \Big\|_{k=1}^{K} \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij}^k W^k h_j\right)\]

여기서 \(K\)는 어텐션 헤드 수, \(\|\)는 헤드별 출력의 연결이다. 마지막 레이어에서는 연결 대신 평균을 사용하는 것이 일반적이다.

특성	GCN	GAT
이웃 가중치	차수 기반 고정	어텐션으로 학습
계산 비용	낮음	상대적으로 높음
귀납적 학습	제한적	가능
이웃 중요도	동일 취급	차별적 취급

GraphSAGE (Sample and Aggregate)¶

Hamilton et al. (2017)이 제안한 GraphSAGE는 두 가지 핵심 혁신을 도입하였다:

샘플링 (Sampling): 모든 이웃 대신 고정 수의 이웃을 샘플링하여 미니배치 학습 가능
귀납적 학습 (Inductive Learning): 학습 시 보지 못한 새 노드에도 적용 가능

갱신 공식:

\[h_i^{(l+1)} = \sigma\left(W^{(l)} \cdot \text{CONCAT}\left(h_i^{(l)},\ \text{AGG}\left(\{h_j^{(l)} : j \in \mathcal{N}_s(i)\}\right)\right)\right)\]

여기서 \(\mathcal{N}_s(i)\)는 노드 \(i\)의 샘플링된 이웃 부분집합이다.

AGG로는 mean, LSTM, max-pooling 등을 사용할 수 있으며, 자기 자신의 표현과 이웃 집계 결과를 명시적으로 연결(CONCAT)하는 점이 GCN과의 주요 차이이다.

GIN (Graph Isomorphism Network)¶

Xu et al. (2019)은 GNN의 표현력을 이론적으로 분석하여, 바이스파르-레만 (Weisfeiler-Leman, WL) 동형 테스트와의 연결을 밝혔다.

핵심 결과: 집계 함수에 따른 표현력 순서:

\[\text{sum} > \text{mean} > \text{max}\]

sum: 다중 집합(multiset)을 완전히 구분 (WL 테스트와 동등)
mean: 분포(proportion)만 구분 가능
max: 집합(존재 여부)만 구분 가능

GIN 갱신 공식:

\[h_i^{(l+1)} = \text{MLP}^{(l)}\left((1 + \epsilon^{(l)}) \cdot h_i^{(l)} + \sum_{j \in \mathcal{N}(i)} h_j^{(l)}\right)\]

여기서 \(\epsilon\)은 학습 가능한 스칼라 또는 고정값이다.

GNN 알고리즘 분류¶

graph TD
    GNN["그래프 신경망 (GNN)"]
    GNN --> Spectral["스펙트럴 기반"]
    GNN --> Spatial["공간적 기반"]
    GNN --> Attention["어텐션 기반"]
    GNN --> Message["메시지 전달 일반화"]

    Spectral --> ChebNet["ChebNet"]
    Spectral --> GCNs["GCN"]

    Spatial --> SAGE["GraphSAGE"]
    Spatial --> GINs["GIN"]

    Attention --> GATs["GAT"]
    Attention --> GATv2["GATv2"]

    Message --> MPNN["MPNN"]
    Message --> PNA["PNA"]

과도한 평활화 문제 (Over-smoothing)¶

GNN을 깊게 쌓으면 모든 노드의 표현이 서로 유사해지는 과도한 평활화 (Over-smoothing) 현상이 발생한다.

수학적 직관: \(k\)-레이어 GCN은 정규화된 인접 행렬을 \(k\)번 곱하는 것과 유사하다. 행렬의 거듭제곱은 정상 분포(stationary distribution)로 수렴하므로, 깊어질수록 노드 표현이 동질화된다.

해결 방법 6가지:

방법	핵심 아이디어
잔차 연결 (Residual Connection)	\(h_i^{(l+1)} = h_i^{(l+1)} + h_i^{(l)}\), 초기 정보 보존
JK-Net (Jumping Knowledge)	모든 레이어의 출력을 결합하여 최종 표현 생성
DropEdge	학습 시 간선을 무작위 제거하여 정보 전파 속도 제한
PairNorm	노드 표현의 쌍별 거리를 유지하도록 정규화
깊이 제한	실무적으로 2~4 레이어가 최적인 경우가 많음
DeeperGCN	Generalized aggregation + pre-activation residual로 깊은 GNN 가능

언제 사용하는가 / 언제 피하는가¶

사용하기 좋은 경우¶

소셜 네트워크 분석: 커뮤니티 탐지, 영향력 전파, 봇 탐지
분자/화학 구조: 약물 발견, 독성 예측, 분자 성질 예측
추천 시스템: 사용자-아이템 이분 그래프 기반 협업 필터링
지식 그래프 (Knowledge Graph): 관계 추론, 엔티티 분류, 링크 예측
교통 네트워크: 교통량 예측, 경로 최적화
코드 분석: AST(추상 구문 트리) 기반 버그 탐지

피해야 하는 경우¶

자연스러운 그래프 구조가 없는 데이터: 무리하게 그래프를 구성하면 노이즈만 추가된다
단순한 그래프 통계로 충분한 경우: 차수 분포, 중심성 등 전통 지표로 해결되면 GNN은 과잉
매우 밀집된 그래프 (Dense Graph): 이웃 수가 극단적으로 많으면 메시지 전달 비용이 폭증하고, 정보 과부하로 오히려 성능이 저하된다
노드 수가 매우 적은 경우: 수십 개 노드의 소규모 그래프에서는 전통적 그래프 알고리즘이 더 해석 가능하고 효과적이다

흔한 오해와 함정¶

1. "그래프 데이터면 항상 GNN이 최선이다"¶

차수(degree), PageRank, 중심성(centrality) 등 수작업 특성을 추출한 후 XGBoost를 적용하는 것이 GNN보다 나은 경우가 꽤 많다. 특히 데이터가 적거나 그래프 구조가 약할 때 그렇다.

2. "레이어를 깊게 쌓으면 더 잘 될 것이다"¶

CNN과 달리 GNN은 2~4 레이어가 대부분의 태스크에서 최적이다. 과도한 평활화로 인해 깊은 GNN은 오히려 성능이 하락한다.

3. "어텐션 가중치가 해석 가능성을 제공한다"¶

GAT의 어텐션 가중치가 높다고 해서 해당 이웃이 예측에 "중요"한 것은 아니다. 어텐션은 모델의 내부 메커니즘이지, 인과적 설명이 아니다. 이는 어텐션 메커니즘에서 다루는 일반적 한계와 동일하다.

4. "링크 예측에서 데이터 누수에 주의하지 않는다"¶

링크 예측 태스크에서는 메시지 전달 간선과 예측 대상 간선을 반드시 분리해야 한다. 예측할 간선이 메시지 전달에도 사용되면 심각한 데이터 누수 (Data Leakage)가 발생한다. 자세한 내용은 데이터 누수를 참고한다.

5. "그래프 구성은 중요하지 않다"¶

GNN의 성능은 입력 그래프의 품질에 크게 좌우된다. kNN 그래프, 임계값 기반 그래프 등 구성 방법에 따라 결과가 크게 달라지므로, 그래프 구성 자체가 중요한 설계 결정이다.

6. "GNN은 확장성이 좋다"¶

전체 그래프에 대한 메시지 전달은 \(O(|E| \cdot d)\) 비용이 들며, 수백만 노드 규모에서는 메모리와 계산 비용 문제가 심각하다. GraphSAGE의 이웃 샘플링, ClusterGCN의 서브그래프 학습 등 확장 기법이 필수적이다.

다른 주제와의 연결¶

신경망 기초: GNN의 기본 구성 요소(MLP, 활성화, 역전파)를 이해하려면 필수
어텐션 메커니즘: GAT의 어텐션 계수 계산은 Transformer의 어텐션과 동일한 원리
Transformer: Graph Transformer는 GNN과 Transformer를 결합한 최신 방향
앙상블 방법: GNN 출력 + 수작업 그래프 특성을 앙상블하면 종종 성능이 향상된다
차원 축소: 노드 임베딩은 그래프의 비선형 차원 축소로 볼 수 있다
특성 공학: 그래프 구성 및 노드/간선 특성 설계가 성능에 결정적
전이 학습: 사전 학습된 GNN을 다운스트림 그래프 태스크에 전이하는 연구가 활발
데이터 누수: 링크 예측에서의 정보 누수 문제

참고 문헌¶

Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
Velickovic, P. et al. (2018). Graph Attention Networks. ICLR.
Hamilton, W. L. et al. (2017). Inductive Representation Learning on Large Graphs. NeurIPS.
Xu, K. et al. (2019). How Powerful are Graph Neural Networks? ICLR.
Gilmer, J. et al. (2017). Neural Message Passing for Quantum Chemistry. ICML.