그래프 신경망(GNN)Graph Neural Network
노드마다 이웃 노드의 특징을 모아 자기 특징과 합쳐 새 특징을 만드는 메시지 전달 계층을 쌓아, 연결 구조가 있는 데이터에서 노드 · 엣지 · 그래프 전체의 표현을 학습하는 신경망이다.
1요약
- 그래프 신경망은 딥러닝 모델 구조 가운데 노드가 이웃의 특징을 모아 자기 특징을 고치는 메시지 전달 계층을 쌓는 구조로, Scarselli 외(2009)가 틀을 내고 Kipf · Welling 의 GCN(2016)이 널리 퍼뜨렸으며, 그 위에서 노드 분류 · 링크 예측 · 분자 성질 예측이 돈다.
- 이웃 수가 노드마다 다르고 순서가 없는 데이터는 격자용 합성곱이나 순서용 순환 계층에 그대로 넣을 수 없는데, 레이블이 노드의 5.2% 뿐인 인용망 Cora 에서 GCN 은 정확도 81.5% 로 레이블 전파(68.0%)를 앞섰다(Kipf 2016 표 1 · 표 2).
- 「계층을 늘렸더니 나빠졌다」는 노드 표현 사이 유사도로 가른다 — 서로 다른 무리 노드끼리의 유사도가 1 에 붙으면 과평활, 유사도는 갈려 있는데 먼 노드 정보가 필요한 과제에서만 떨어지면 과압축, 학습 정확도만 높으면 과적합이다.
2등장 배경
분자(원자 = 노드 · 결합 = 엣지), 논문 인용망, 친구 관계망은 노드마다 이웃 수가 다르고 노드에 정해진 순서가 없다. 이런 데이터를 고정 길이 벡터로 펴려면 사람이 분자 지문 · 연결 지표를 골라야 했고, 노드 번호를 바꿔 매기면 같은 그래프가 다른 입력이 되었다.
Gori · Monfardini · Scarselli(2005)와 Scarselli 외(2009)는 노드 상태를 이웃 상태로 고정점에 이를 때까지 되풀이 갱신하는 첫 GNN 모델을 냈다. 2013년 Bruna 외는 그래프 라플라시안의 고유벡터로 합성곱을 정의했고(Bruna 2013), 2016년 Kipf · Welling 은 이를 1차 근사하고 자기 고리를 더한 Ã = A + I 정규화로 계층 하나를 행렬 곱 한 줄로 줄였다(Kipf 2016 식 8). 2017년 Gilmer 외는 메시지 · 갱신 · 읽기 세 함수로 여러 모델을 한 틀(MPNN)로 묶어 분자 자료 QM9 의 13 개 성질 가운데 11 개에서 화학적 정확도에 들었다(Gilmer 2017 1절).
같은 해 GraphSAGE(이웃 표본 추출 · 새 노드 추론)와 GAT(이웃별 어텐션 가중치)가 나왔고, 2018년 Xu 외는 메시지 전달 GNN 의 구분력이 WL 그래프 동형 검정을 넘지 못함을 보였다(Xu 2018). 지금은 메시지 전달이 표준 틀이고, 깊이 쌓을 때의 과평활(Li 2018)과 먼 노드 정보가 눌리는 과압축(Alon 2020)이 남은 한계다.
3쉽게 이해하기 — 섬마을 저녁 쪽지
섬마을 집들은 길로 이어진 이웃끼리만 저녁마다 쪽지를 주고받는다. 각 집은 받은 쪽지를 자기 메모와 섞어 새 메모를 쓰는데, 이웃이 많은 집이 보낸 쪽지는 옅게 섞는다. 이틀 밤이 지나면 이웃의 이웃 소식까지 메모에 담기고, 이장은 어느 편인지 알려진 두 집만 보고 나머지 집의 편을 메모로 맞힌다. 그런데 서른 밤 넘게 돌리면 모든 집 메모가 똑같아져 편을 가를 수 없다.
그림 1 · 집은 길로 이어진 이웃에게서만 쪽지를 받아 메모를 고치고, 둘째 밤에는 이웃의 이웃 소식까지 받아 이장이 편을 맞힌다.
그림 2 · 쪽지를 두세 밤 돌리면 같은 편 메모끼리 닮아 편이 갈리지만, 서른 밤을 넘기면 모든 메모가 같아져 다시 가를 수 없다.
| 비유 속 역할 | GNN 요소 | 실제로 하는 일 |
|---|---|---|
| 집 | 노드 v | 특징 벡터 h_ |
| 길 | 엣지 · 인접 행렬 A | 누가 누구와 이어졌는지 · 이어진 노드끼리만 계산 |
| 쪽지 | 메시지 M | 이웃 u 의 특징 h_ |
| 옅게 섞기 | 정규화 집계 | 차수로 나눈 가중 합(GCN) · 평균 · 어텐션 |
| 메모 고치기 | 갱신 U | 가중치 W 곱 + 활성 함수로 새 h_ |
| 하룻밤 | 계층 하나 | 계층 K 개 = K홉 안 노드만 반영 |
| 편이 알려진 집 | 레이블 노드 | 손실을 계산하는 노드(사례 34명 중 2명) |
| 이장의 판단 | 출력 헤드 | 노드 분류 · 링크 예측 · 그래프 성질 예측 |
⚠ 비유가 맞지 않는 곳: 마을 사람은 쪽지 내용을 골라 읽지만, GCN 은 이웃 메시지를 차수로만 정한 고정 비율로 더한다(골라 읽기는 GAT 의 어텐션). 또 밤마다 메모 적는 법이 같아 보이지만, 실제로는 계층마다 다른 가중치 W 를 쓴다.
4구조 — 메시지 · 집계 · 갱신 · 읽기
GNN 계층 하나는 이웃에게서 메시지를 받고(M), 모으고(AGG), 자기 표현과 합쳐 고친다(U). Gilmer 외는 이를 h_v′ = U(h_v, Σ_u∈N(v) M(h_v, h_u, e_uv)) 로 묶었고(Gilmer 2017 식 1 · 2), GCN 은 이 틀을 H′ = σ(D̃^−1/2 Ã D̃^−1/2 H W) 한 줄로 쓴다(Kipf 2016 식 2). 그래프 전체를 하나의 값으로 낼 때는 계층 끝에 노드 표현을 합 · 평균으로 모으는 읽기(readout)를 붙인다.
그림 3 · GNN 은 입력 그래프의 노드 특징을 메시지 · 집계 · 갱신 계층에 L번 통과시켜 L홉 안 이웃이 섞인 노드 표현을 만들고, 그 표현을 노드 · 엣지 · 그래프 세 수준의 헤드가 나눠 쓴다.
| 요소 | 크기(사례) | 역할 | 값 · 근거 |
|---|---|---|---|
| 노드 특징 X | 34 × 34 | 노드마다 입력 벡터 | 특징이 없으면 단위 행렬(Kipf 2016 부록 A) |
| 인접 행렬 A | 34 × 34 · 엣지 78 | 메시지가 오가는 길 | Ã = A + I 로 자기 메시지 포함(Kipf 2016 식 8) |
| 정규화 집계 | Â = D̃^−1/2 Ã D̃^−1/2 | 이웃 메시지를 섞는 비율 | 노드 i · j 가중치 1/√(d̃_i d̃_j) |
| 갱신 W · σ | 34 × 16 · 16 × 2 | 계층마다 특징 변환 | 가중치 576개 · 모든 노드가 같은 W 공유 |
| 노드 표현 H | 34 × 16 | 이웃이 섞인 특징 | 계층 K 개 = K홉 안 노드만 반영 |
| 읽기 · 헤드 | 노드 · 엣지 · 그래프 | 과제별 출력 | 합 읽기 = 구분력 최대(Xu 2018 4.2절) |
🔑 계층 하나가 이웃 한 홉이다 — K 계층 GNN 의 노드 표현은 K홉 안 노드만으로 정해지고, 그 밖의 노드는 아무리 중요해도 표현에 들어오지 않는다.
5동작 — 가라테 클럽 34명의 편 맞히기
사례는 Python 3.14.0 · NumPy 2.4.3 · default_rng(0) 으로 2계층 GCN 과 Adam 을 직접 구현해, Zachary(1977)의 가라테 클럽 친분 그래프(NetworkX 소스의 행렬 · 34명 · 엣지 78)에서 돌렸다. 클럽은 사범 편 17명 · 관리자 편 17명으로 갈렸다.
- 입력 — 사람마다 특징이 없으므로 X = 34 × 34 단위 행렬로 두고, 편을 알려 주는 레이블은 노드 0(사범) · 노드 33(관리자) 둘뿐이다.
- 정규화 — Ã = A + I 의 행을 1/√(d̃_i d̃_j) 로 나눈다. 노드 8(이웃 0 · 2 · 30 · 32 · 33)의 행은 자기 0.167 · 노드 30 0.183(이웃 4명) · 노드 33 0.096(이웃 17명)으로, 이웃이 많은 노드의 메시지가 옅다.
- 1계층 — H1 = ReLU(Â X W0) · W0 = 34 × 16 이고, 노드 8 의 16 값은 자기와 이웃 다섯의 W0 행을 2단계 비율로 더한 것이다.
- 2계층 — Z = softmax(Â H1 W1) · W1 = 16 × 2 이고, 2계층을 거친 노드 8 의 출력에는 2홉 안 31명의 특징이 섞인다.
- 학습 — 레이블 노드 둘의 교차 엔트로피만 쓰고 Adam 학습률 0.01 · 첫 계층 L2 5 × 10^−4 로 200 에폭 돌리면 손실이 0.705 → 0.003 으로 준다.
- 결과 — 레이블 없는 32명 중 30명(93.8%)을 맞힌다. 틀린 둘은 노드 2(사범 0.493 · 관리자 0.507)와 노드 8(관리자 0.818)이고, 노드 8 은 이웃 다섯 중 셋이 관리자 편이다.
- 대조 — 같은 크기의 MLP(Â 대신 I)는 32명 중 16명만 맞힌다. 레이블 없는 노드의 입력 행은 기울기가 0 이라 한 번도 학습되지 않기 때문이다(시드 0 ~ 9 범위 GCN 30 ~ 31명 · MLP 10 ~ 20명).
그림 4 · 노드 8 의 출력은 2계층을 거치며 이웃 다섯과 그 이웃(2홉 31명)의 정보를 차수로 정한 비율로 받고, 이웃 다수가 관리자 편이라 관리자 편으로 잘못 기운다.
그림 5 · 전파를 2 ~ 4번 하면 같은 편끼리만 닮아 두 편의 간격이 가장 넓고, 16번을 넘기면 다른 편끼리도 유사도가 1 에 붙어 간격이 사라진다 — 이것이 과평활이다.
🔑 메시지 전달은 이웃끼리 표현을 닮게 만드는 평활이다 — 두세 번은 같은 편을 모으지만 수십 번이면 다른 편까지 한 값으로 섞으므로, 깊이가 힘이 되는 합성곱 신경망과 달리 GNN 은 2 ~ 3계층으로 얕게 쌓는다(Kipf 2016 부록 B · Li 2018).
6비교 — 이웃을 모으는 방식에 따른 변종
| 방식 | 이웃 집계 | 이웃 가중치 | 새 노드 추론 | 성질 · 근거 |
|---|---|---|---|---|
| GCN | 정규화 합 | 차수로 고정 1/√(d̃_i d̃_j) | 전체 그래프 행렬 필요 | Cora 81.5%(Kipf 2016 표 2) |
| GraphSAGE | 표본 이웃의 평균 · 풀링 · LSTM | 고정 | 됨(귀납) | 표본 S1 = 25 · S2 = 10(Hamilton 2017 4절) |
| GAT | 어텐션 가중 합 | 학습 · 헤드 8 | 됨 | Cora 83.0%(Veličković 2017 표 2) |
| GIN | 합 + MLP | 고정 · 자기 1 + ε | 됨 | 구분력 = WL 검정(Xu 2018 정리 3) |
| MPNN | 메시지 함수 일반형 | 엣지 특징 e_ | 됨 | QM9 13 중 11 화학적 정확도(Gilmer 2017) |
| 합성곱 · 트랜스포머 | 격자 이웃 칸 9개 · 모든 토큰 쌍 | 위치별 가중치 · 어텐션 | — | 그래프가 격자 · 완전 그래프인 특수한 경우 |
분석노드 특징과 연결이 고정된 그래프면 GCN 으로 기준선을 재고, 새 노드가 계속 들어오면 GraphSAGE, 이웃마다 중요도가 다르면 GAT, 분자처럼 그래프 전체 구조를 구분해야 하면 합 집계 GIN · 엣지 특징이 있으면 MPNN 을 고른다. 근거는 표의 집계 · 추론 열 — 평균 · 최대 집계는 이웃 구성이 다른 그래프를 같은 값으로 보낼 수 있다(Xu 2018 5.2절).
7실무 진단 — 성능 저하를 데이터 · 깊이 · 집계로 가르기
분석엣지 동질 비율 → 계층별 표현 유사도 → 집계 함수 → 학습 곡선 순으로 본다. GNN 은 이웃이 같은 무리라는 가정 위에서 동작하므로(Zhu 2020 1절), 이 가정이 깨진 데이터에서 계층 · 집계를 바꾸면 원인을 놓친다.
| # | 증상 | 의심 원인 | 단계 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 그래프를 안 쓴 MLP 보다 낮음 | 이질성(이웃이 다른 무리) | 데이터 | 엣지 동질 비율 | 사례 0.86 · 노드 8 처럼 이웃 다수가 다른 편이면 틀림(Zhu 2020) |
| 2 | 계층을 늘리자 정확도 하락 | 과평활 | 깊이 | 같은 · 다른 무리 쌍의 표현 유사도 | 간격이 0 에 가까우면 과평활(사례 k = 16 · 0.05 · Li 2018) |
| 3 | 먼 노드 정보가 필요한 과제만 낮음 | 과압축 | 수용 범위 | 정답에 필요한 홉 수 ↔ 계층 수 | 계층을 늘려도 학습 정확도가 안 오름(Alon 2020) |
| 4 | 구조가 다른 그래프를 같은 값으로 출력 | 평균 · 최대 집계의 구분력 | 집계 | 합 집계로 바꾼 결과 | 합으로 갈리면 집계가 원인(Xu 2018 5.2절) |
| 5 | 학습 정확도만 높음 | 과적합 · 레이블 부족 | 학습 | 학습 · 검증 곡선 | 7계층을 넘으면 잔차 연결 없이 학습이 어려움(Kipf 2016 부록 B) |
| 6 | 허브 노드에서 메모리 초과 | 이웃 폭발 | 미니배치 | 계층별 이웃 수 | 표본 S1 · S2 ≤ 500 으로 제한(Hamilton 2017 3.1절) |
깊이를 바꿀 때는 시드 여러 개로 잰다. 사례에서 레이블 없는 32명 중 맞힌 수의 시드 0 ~ 9 평균은 1계층 30.4 · 2계층 30.9 · 8계층 29.6 · 16계층 26.8(최소 16)으로, 깊어질수록 평균보다 최솟값이 먼저 무너졌다.
8시험 대비
www.q-net.or.kr시험에서는 구성 요소와 동작 원리를 묻는 정의 · 특징형, 그리고 합성곱 신경망 · 트랜스포머 또는 GCN · GAT · GraphSAGE 와의 차이를 묻는 비교형이 나올 수 있다. 「그래프를 다루는 신경망」 한 줄에서 그치지 않고 «메시지 · 집계 · 갱신을 몇 홉까지 반복하는가»를 축으로 쓰면 한계(과평활)까지 한 답안이 된다.
- 개요 — 정의 · 입력 데이터(노드 · 엣지 · 인접 행렬) · 격자 · 순서 데이터와의 차이
- 구조 — 그림 3 메시지 M · 집계 AGG · 갱신 U · 읽기 · 세 수준 헤드 · GCN 식 Â H W
- 동작 — 그림 4 노드 8 의 2계층 계산(정규화 가중치 0.167 · 0.096 · 2홉 31명) · 사례 32명 중 30명
- 핵심 원리 — 그림 5 과평활 곡선(간격 k = 3 0.39 → k = 16 0.05) · K 계층 = K홉
- 변종 비교 — GCN · GraphSAGE · GAT · GIN · MPNN 표(집계 · 가중치 · 귀납)
- 한계와 동향 — 과평활 · 과압축 · 이질성 · WL 검정 상한 · 분자 · 추천 · 교통망 활용
꼭 쓸 키워드
메시지 전달이웃 집계인접 행렬정규화GCNGATGraphSAGEGIN과평활수용 범위
다른 답안과 차이를 내는 한 가지는 그림 5 처럼 «같은 편 ↔ 다른 편 유사도» 두 곡선을 나란히 보이는 것이다 — 간격이 커졌다가 사라지는 그래프가 「GNN 은 왜 얕게 쌓는가」를 숫자로 보인다.
9오해와 사실
- 오해GNN 도 계층을 깊게 쌓을수록 성능이 오른다.사실Kipf · Welling 의 깊이 실험에서는 2 ~ 3계층이 가장 좋았고 7계층을 넘으면 잔차 연결 없이 학습이 어려웠다(Kipf 2016 부록 B).
- 오해그래프만 있으면 GNN 이 그래프를 안 쓰는 모델보다 낫다.사실이웃이 다른 무리인 이질성 그래프에서는 MLP 가 더 나은 경우가 보고되었고(Zhu 2020), 사례의 노드 8 도 이웃 다수의 편으로 끌려 틀렸다.
- 오해GNN 은 어떤 두 그래프든 구별할 수 있다.사실메시지 전달 GNN 의 구분력은 1차 WL 검정을 넘지 못하며, 합 집계일 때 그 상한에 이른다(Xu 2018 보조정리 2 · 정리 3).
10핵심 정리
| 구분 | 맡는 일 | 식 · 장치 | 사례 값 | 근거 |
|---|---|---|---|---|
| 그래프 입력 | 노드 특징 · 연결 | X · A · Ã = A + I | 34명 · 엣지 78 | Zachary 1977 |
| 정규화 집계 | 이웃 메시지 섞기 | 1/√(d̃_i d̃_j) | 노드 8 자기 0.167 · 노드 33 0.096 | Kipf 2016 식 8 |
| 갱신 | 계층별 특징 변환 | σ(Â H W) | 가중치 576개 | Kipf 2016 식 2 |
| 노드 표현 | K홉 정보 요약 | 계층 K = K홉 | 2계층 = 31명 | Gilmer 2017 |
| 출력 헤드 | 노드 · 엣지 · 그래프 과제 | softmax · 내적 · 읽기 | 32명 중 30명 · MLP 16명 | Kipf 2016 |
| 과평활 | 깊이의 한계 | Â^k X → 한 방향 | 간격 k = 3 0.39 → k = 16 0.05 | Li 2018 |
| 과압축 | 먼 정보의 손실 | 고정 크기 벡터 병목 | 이 사례 미측정 | Alon 2020 |
| 구분력 | 다른 그래프 가르기 | 합 집계 ≤ WL 검정 | 이 사례 미측정 | Xu 2018 |
11참고 문헌
- 먼저 볼 문헌
- ★ Semi-Supervised Classification with Graph Convolutional Networks (Kipf · Welling) — GCN 계층 식(식 2 · 8)과 재정규화 · Cora 결과(표 2) · 깊이 실험(부록 B)을 볼 때
- ★ Neural Message Passing for Quantum Chemistry (Gilmer et al.) — 메시지 · 갱신 · 읽기 세 함수로 여러 GNN 을 한 틀로 묶는 식을 볼 때
- ★ How Powerful are Graph Neural Networks? (Xu et al.) — 합 · 평균 · 최대 집계의 구분력과 WL 검정 상한을 볼 때
- ★ Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (Li · Han · Wu) — GCN 이 라플라시안 평활이고 깊이 쌓으면 과평활이 되는 이유를 볼 때
- 본문 근거
- The Graph Neural Network Model (IEEE Transactions on Neural Networks 20(1) 61-80) — IEEE · 2009-01 ·
doi.org/10.1109/TNN.2008.2005605· 확인 2026-11-12 - A new model for learning in graph domains (IJCNN 2005 vol. 2 729-734) — IEEE · 2005-07 ·
doi.org/10.1109/IJCNN.2005.1555942· 확인 2026-11-12 - Spectral Networks and Locally Connected Networks on Graphs (Bruna et al.) — arXiv · ICLR 2014 · 2013-12 ·
arxiv.org/abs/1312.6203· 확인 2026-11-12 - Inductive Representation Learning on Large Graphs (Hamilton · Ying · Leskovec) — arXiv · NIPS 2017 · 2017-06 ·
arxiv.org/abs/1706.02216· 확인 2026-11-12 - Graph Attention Networks (Veličković et al.) — arXiv · ICLR 2018 · 2017-10 ·
arxiv.org/abs/1710.10903· 확인 2026-11-12 - On the Bottleneck of Graph Neural Networks and its Practical Implications (Alon · Yahav) — arXiv · ICLR 2021 · 2020-06 ·
arxiv.org/abs/2006.05205· 확인 2026-11-12 - Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs (Zhu et al.) — arXiv · NeurIPS 2020 · 2020-06 ·
arxiv.org/abs/2006.11468· 확인 2026-11-12 - An Information Flow Model for Conflict and Fission in Small Groups (Journal of Anthropological Research 33(4) 452-473) — University of Chicago Press · 1977-12 ·
doi.org/10.1086/jar.33.4.3629752· 확인 2026-11-12 - NetworkX source - networkx/generators/social.py (karate_club_graph) — NetworkX Developers · 2026-11 ·
github.com/networkx/networkx/blob/main/networkx/generators/social.py· 확인 2026-11-12 - NumPy 2.4 Reference Random Generator — NumPy Developers · 2026-11 ·
numpy.org/doc/stable/reference/random/generator.html· 확인 2026-11-12