그래프 신경망 (Graph Neural Networks)

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

핵심 요약: 그래프 신경망(GNN, Graph Neural Network)은 소셜 네트워크(Social Network), 분자 구조(Molecular Structure) 등 관계(그래프) 데이터를 처리하는 신경망이다. 핵심은 메시지 패싱(Message Passing): 각 노드(Node)가 이웃의 정보를 모아 자신의 표현(Representation)을 갱신한다.

핵심 용어 미리보기:

노드 (Node): 그래프의 꼭짓점. 사람, 원자, 웹페이지 등 개체를 나타낸다
간선 (Edge): 노드 사이의 연결. 친구 관계, 화학 결합, 하이퍼링크 등을 나타낸다
메시지 패싱 (Message Passing): 각 노드가 이웃 노드의 정보(메시지)를 모아 자신의 표현을 갱신하는 과정
수용 영역 (Receptive Field): $k$ 번의 메시지 패싱 후 한 노드가 정보를 받을 수 있는 $k$ -홉(hop) 이웃 범위
과도한 평활화 (Over-smoothing): GNN을 너무 깊게 쌓으면 모든 노드의 표현이 비슷해지는 문제

개요

현실 세계의 많은 데이터는 그래프 (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.)으로 이어지며 빠르게 발전하였다.

탄생 배경

그래프 신경망의 역사는 “그래프에서 어떻게 딥러닝을 할 것인가”라는 질문에 대한 답을 찾는 여정이다. 2005년 Gori et al.이 그래프에 신경망을 적용하는 초기 연구를 발표했지만, 당시에는 계산 비용과 학습 불안정성으로 큰 주목을 받지 못하였다.

전환점은 2017년 Kipf와 Welling이 GCN (Graph Convolutional Network)을 발표하면서 찾아왔다. 스펙트럴 그래프 이론에서 출발하여 놀라울 정도로 단순하고 효과적인 공식 하나로 귀결시킨 이 논문은, 그래프 딥러닝 연구의 폭발적 성장을 촉발하였다. 같은 해 Hamilton et al.의 GraphSAGE가 귀납적 학습과 이웃 샘플링으로 확장성 문제를 해결하였고, 2018년에는 Velickovic et al.의 GAT (Graph Attention Network)가 이웃 노드에 차별적 가중치를 부여하는 어텐션 메커니즘을 도입하였다.

2019년 Xu et al.은 GIN (Graph Isomorphism Network)으로 GNN의 표현력을 이론적으로 분석하며, 어떤 집계 함수가 가장 강력한지를 WL 테스트(Weisfeiler-Leman test)와의 연결을 통해 밝혀냈다. 이후 Graph Transformer, 이종 그래프(Heterogeneous Graph) GNN, 시공간 GNN 등으로 빠르게 확장되고 있다.

Gori (2005) → GCN (2017) → GraphSAGE (2017) → GAT (2018) → GIN (2019) → Graph Transformer (2020~). 핵심 경쟁은 “더 강력한 표현력”과 “더 나은 확장성” 사이의 균형이다.

핵심 개념

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을 통합하는 일반적 관점을 제공한다. 직관적으로 비유하면, 메시지 패싱은 소문 전파와 같다. 각 노드가 이웃의 소문(메시지)을 듣고, 그 정보를 종합하여 자신의 의견(표현)을 업데이트한다. 소문이 여러 번 전파되면 멀리 떨어진 노드의 정보까지 간접적으로 도달하게 되는데, 이것이 GNN의 수용 영역(receptive field) 확장 원리이다.

각 레이어에서 세 단계가 반복된다:

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)})$

숫자로 이해하기

3개 노드(Node) A, B, C로 이루어진 간단한 그래프를 생각하자. 간선(Edge): A—B, B—C (A와 C는 직접 연결 없음).

초기 특성(Feature): $h_A = [1, 0]$ , $h_B = [0, 1]$ , $h_C = [1, 1]$

메시지 패싱(Message Passing) 1단계 (평균 집계, Mean Aggregation):

노드 A의 이웃: {B} → 집계 = $[0, 1]$ → 갱신: $h_A' = [1, 0] + [0, 1] = [1, 1]$
노드 B의 이웃: {A, C} → 집계 = $([1, 0] + [1, 1]) / 2 = [1, 0.5]$ → 갱신: $h_B' = [0, 1] + [1, 0.5] = [1, 1.5]$
노드 C의 이웃: {B} → 집계 = $[0, 1]$ → 갱신: $h_C' = [1, 1] + [0, 1] = [1, 2]$

1단계만으로 A는 B의 정보를, C도 B의 정보를 흡수했다. 2단계를 거치면 A는 C의 정보까지 (B를 경유하여) 간접적으로 받게 된다 — 이것이 수용 영역(Receptive Field) 확장이다.

2. 메시지 전달 프레임워크 (Message Passing) 다이어그램

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 알고리즘 분류

GNN 알고리즘 분류 다이어그램

과도한 평활화 문제 (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): 이웃 수가 극단적으로 많으면 메시지 전달 비용이 폭증하고, 정보 과부하로 오히려 성능이 저하된다
노드 수가 매우 적은 경우: 수십 개 노드의 소규모 그래프에서는 전통적 그래프 알고리즘이 더 해석 가능하고 효과적이다

실전 사례

약물 발견 (Drug Discovery)에서 GNN의 혁신

신약 개발에서 가장 중요한 초기 단계는 수백만 개의 후보 분자 중에서 약효가 있고 독성이 낮은 분자를 골라내는 것이다. 분자는 본질적으로 그래프 구조를 가진다 — 원자가 노드이고, 화학 결합이 간선이다. 이 자연스러운 대응 덕분에 GNN은 분자 특성 예측에 탁월한 성능을 보인다.

사례 — MIT의 Chemprop: MIT의 연구팀은 메시지 전달 신경망(MPNN) 기반의 Chemprop 모델을 개발하여, 기존의 분자 지문(molecular fingerprint) + 랜덤 포레스트 조합을 능가하는 성능을 다수의 분자 성질 예측 벤치마크에서 달성하였다. 특히 항생제 발견 연구에서는 GNN이 기존 항생제와 구조적으로 전혀 다른 새로운 항생제 후보 물질 “할리신(Halicin)“을 발견하는 데 기여하였다 (Stokes et al., 2020, Cell).

왜 GNN이 효과적인가: 전통적인 분자 표현(SMILES 문자열, 분자 지문)은 분자의 2D 또는 3D 구조 정보를 불완전하게 인코딩한다. 반면 GNN은 원자 간의 결합 관계, 원자 유형, 결합 유형 등을 그래프의 노드/간선 특성으로 직접 반영하여, 분자의 구조적 패턴을 계층적으로 학습할 수 있다. 메시지 전달의 각 단계가 화학적 “관능기(functional group)” 수준의 특성을 포착하는 것으로 해석될 수 있다.

흔한 오해와 함정

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.