그래프 신경망 입문: 메시지 전달 · GCN · GraphSAGE · GAT

그래프 신경망 입문: 메시지 전달 · GCN · GraphSAGE · GAT

친구 관계, 분자 구조, 논문 인용, 상품-구매자 관계처럼 "무엇과 무엇이 연결되어 있다"는 데이터는 표나 이미지로는 담기 어렵습니다. 그래프 신경망(GNN, graph neural network)은 각 점(노드)이 이웃에게서 정보를 받아 자기 표현을 고치는 메시지 전달 을 층마다 되풀이합니다. 이 수업은 노드 3개짜리 그래프로 GCN의 정규화 행렬을 손으로 계산하고, GraphSAGE · GAT의 차이와 깊게 쌓을 때의 함정(과평활화)까지 정리합니다.

들어가기 전에

• 머신러닝을 위한 수학 — 행렬 곱, 대각 행렬, 고윳값
• 임베딩과 벡터 유사도 — 노드를 벡터로 나타낸다는 생각
• 스탠퍼드 CS231n 강의 노트(합성곱 신경망) — '이웃 픽셀을 가중합'하는 합성곱. GNN은 이를 불규칙한 이웃으로 넓힌 것입니다.
• 어텐션 직관: 쿼리 · 키 · 값을 손으로 계산하기 — GAT 이해에 필요(선택)

한눈에 보기

• 그래프를 인접 행렬로 적고, 노드 · 엣지 · 그래프 수준 과제를 구분할 수 있습니다.
• 메시지 전달의 세 단계(메시지 → 모으기 → 갱신)를 식으로 씁니다.
• GCN 정규화 행렬 $\tilde D^{-1/2}\tilde A\tilde D^{-1/2}$ 를 3노드 그래프로 직접 계산합니다.
• GraphSAGE(샘플링 · 귀납)와 GAT(이웃별 가중치)의 설계 이유를 압니다.
• 층을 많이 쌓으면 노드 표현이 비슷해지는 과평활화를 숫자로 확인합니다.

1. 그래프와 과제의 종류

직관(해설용 비유). 회사 메신저를 떠올립니다. 사람이 노드(node), 대화를 주고받은 관계가 엣지(edge) 입니다. "이 사람이 어느 팀일까"(노드 분류), "이 두 사람이 앞으로 협업할까"(엣지 예측), "이 대화망 전체가 건강한 조직일까"(그래프 분류)를 물을 수 있습니다. Distill 글도 과제를 이 세 수준으로 나눕니다.

인접 행렬(adjacency matrix). 노드 $N$ 개면 $N\times N$ 표 $A$ 를 만들고, $i$ 와 $j$ 가 연결되면 $A_{ij}=1$, 아니면 0입니다.

숫자로 해 보기(해설용). 노드 1–2, 2–3이 연결된 줄 모양 그래프:

노드 2는 이웃이 둘, 노드 1 · 3은 하나입니다. 각 노드에는 특징 벡터(예: 사람의 직급 · 근속 연수, 원자의 종류)가 붙습니다.

순서 불변성 — 왜 그냥 MLP에 넣으면 안 되나. 노드 번호를 1 · 2 · 3 대신 3 · 1 · 2로 바꿔도 같은 그래프입니다. 그런데 인접 행렬을 펼쳐 MLP에 넣으면 번호만 바꿔도 입력이 달라져 다른 답이 나옵니다. 그래서 GNN은 이웃 정보를 합 · 평균 · 최댓값 처럼 순서와 상관없는 연산으로 모읍니다. 또 실제 그래프는 매우 희소해서(대부분 0), 큰 그래프는 행렬 대신 엣지 목록으로 저장하는 경우가 많습니다.

2. 메시지 전달: GNN의 공통 틀

Gilmer 외(ICML 2017)는 여러 그래프 모델을 메시지 전달 신경망(MPNN) 이라는 하나의 틀로 묶었습니다. 분자 성질 예측 벤치마크 QM9에서 실험했습니다.

단계.

1. 메시지: 각 이웃 $w$ 가 "나는 이런 상태"라는 메시지를 만듭니다.
2. 모으기(aggregate): 노드 $v$ 가 이웃 메시지를 순서와 무관하게 합칩니다.
3. 갱신(update): 모은 메시지와 자기 상태로 새 상태를 만듭니다.
4. 이를 $T$ 번 반복한 뒤, 그래프 수준 과제면 모든 노드를 모아 읽어 냅니다(readout).

직관. 층 하나를 지나면 한 칸 떨어진 이웃의 정보가, 세 층이면 세 칸 떨어진 노드의 정보까지 섞입니다(Distill 글의 설명). CNN 층을 쌓을수록 수용 영역이 넓어지는 것과 같습니다.

123456789flowchart LR
  G[그래프<br/>노드 특징 · 엣지] --> M[이웃마다 메시지 만들기]
  M --> AG[모으기<br/>합 · 평균 · 어텐션 가중합]
  AG --> UP[갱신<br/>W 곱 + 비선형]
  UP --> L{층 반복<br/>K번}
  L -->|다음 층| M
  L --> N1[노드 분류<br/>노드 표현 그대로]
  L --> E1[엣지 예측<br/>두 노드 표현 결합]
  L --> R1[그래프 분류<br/>전체 풀링 readout]

3. GCN: 정규화된 이웃 평균

전파식(원 논문 식 (2)). Kipf · Welling(ICLR 2017)의 그래프 합성곱 신경망(GCN)은 한 층을 이렇게 씁니다.

왜 셀프 루프와 정규화를 하나.

• $I$ 를 더하지 않으면 노드가 이웃만 보고 자기 자신의 특징을 잃습니다.
• 정규화하지 않으면 이웃이 많은 노드의 값이 층마다 계속 커집니다. 논문은 원래 식의 연산자를 반복 적용하면 수치가 불안정해지고 기울기가 폭발 · 소실될 수 있어 이 '재정규화 트릭(renormalization trick)'을 도입했다고 설명합니다.
• $1/d_i$ (단순 평균) 대신 $1/\sqrt{d_i d_j}$ 를 쓰면 보내는 쪽과 받는 쪽의 이웃 수를 모두 고려해, 이웃이 아주 많은 '허브' 노드의 영향이 적당히 줄어듭니다.

숫자로 해 보기(해설용, numpy로 확인). 위 줄 모양 그래프에서

1. $\tilde A = A + I$, 행 합 $\tilde d = (2, 3, 2)$
2. 연결마다 $1/\sqrt{d_i d_j}$: $(1,1)\to1/2$, $(1,2)\to1/\sqrt6\approx0.408$, $(2,2)\to1/3$

3. 노드 특징(스칼라) $x = (1, 0, 3)$ 이면 $\hat A x \approx (0.500,\ 1.633,\ 1.500)$ 입니다.
   • 노드 1: $0.5\times1 + 0.408\times0 = 0.5$
   • 노드 2: $0.408\times1 + 0.333\times0 + 0.408\times3 = 1.633$
   • 비교: 자기 포함 단순 평균이면 $(0.5,\ 1.333,\ 1.5)$ 입니다.

특징이 2차원이고 $W$ 를 곱하고 ReLU를 씌우는 것까지가 한 층입니다. 예를 들어 $X = \begin{pmatrix}1&0\\0&1\\1&1\end{pmatrix}$, $W = \begin{pmatrix}1&-1\\0.5&1\end{pmatrix}$ 이면 $\mathrm{ReLU}(\hat A X W) \approx \begin{pmatrix}0.704&0\\1.187&0\\0.954&0.408\end{pmatrix}$ 입니다.

결과(원 논문 표 2). 인용망 Citeseer · Cora · Pubmed에서 정확도 70.3% · 81.5% · 79.0%를 보고했습니다(은닉 16, 드롭아웃 0.5, L2 $5\times10^{-4}$).

4. GraphSAGE: 이웃을 뽑아 쓰고, 처음 보는 노드도 처리하기

문제. GCN 원형은 그래프 전체 행렬로 한 번에 계산하고, 학습 때 본 노드에 맞춰집니다. 매일 새 사용자 · 새 상품이 생기는 서비스에는 맞지 않습니다.

아이디어(Hamilton 외, NeurIPS 2017). 노드마다 따로 임베딩을 외우는 대신, "이웃 특징을 뽑아 모으는 함수" 를 배웁니다. 함수이므로 처음 보는 노드에도 그대로 적용됩니다(귀납적, inductive).

단계(논문 알고리즘 1을 단순화).

1. 이웃 중 일정 개수만 무작위로 뽑습니다(이웃 샘플링).
2. 뽑은 이웃 표현을 모읍니다(평균 · LSTM · 풀링 집계기 중 하나).
3. 자기 표현과 이어 붙여(concat) $W$ 를 곱하고 비선형을 씌운 뒤, 길이를 1로 정규화합니다.

논문은 깊이 $K=2$, 두 단계 샘플 수의 곱 $S_1\cdot S_2 \le 500$ 정도로도 높은 성능을 얻었다고 보고합니다. 왜 샘플링인가: 인기 노드는 이웃이 수백만일 수 있어, 전부 모으면 계산이 폭발합니다. 고정 개수만 뽑으면 노드 하나의 계산량이 일정해집니다.

5. GAT: 이웃마다 다른 가중치

문제. GCN의 가중치 $1/\sqrt{d_id_j}$ 는 그래프 모양으로만 정해집니다. 하지만 이웃마다 중요도가 다를 수 있습니다.

아이디어(Veličković 외, ICLR 2018). 이웃끼리 셀프 어텐션을 해서, 연결된 이웃에만(마스크) 학습된 가중치를 줍니다.

숫자로 해 보기(해설용). 노드 $i$ 의 이웃 세 개(자기 포함) 점수가 $(1, 2, 0)$ 이면 가중치는 $(0.245,\ 0.665,\ 0.090)$ 입니다. 그래프 모양이 같아도 특징에 따라 가중치가 달라집니다. 원 논문은 멀티헤드(Cora 첫 층 8개 헤드)를 쓰고, Cora에서 83.0 ± 0.7%(같은 표의 GCN 81.5%)를 보고했습니다.

6. 과평활화와 활용

과평활화(over-smoothing). 메시지 전달은 본질적으로 '이웃과 평균 내기'라서, 층을 많이 쌓으면 모든 노드 표현이 서로 비슷해집니다.

숫자로 해 보기(해설용, numpy로 확인). 위 $\hat A$ 를 $x=(1,0,3)$ 에 거듭 곱하면

원래 1과 3으로 크게 달랐던 노드 1 · 3이 같아졌습니다. $\hat A$ 의 가장 큰 고윳값이 1이고 그 고유벡터가 $\sqrt{\tilde d}$ 에 비례하기 때문에, 결국 "차수만 반영된 같은 모양"으로 수렴합니다. 그래서 실무 GNN은 보통 2~4층 정도로 얕게 쓰고, 잔차 연결 · 자기 표현 이어 붙이기 같은 장치로 이를 늦춥니다.

활용.

• 분자 · 신약: 원자 = 노드, 결합 = 엣지. 분자 성질 예측(MPNN의 QM9 실험).
• 추천: 사용자 · 상품의 이분 그래프에서 "이 사용자가 이 상품을 살까"(엣지 예측).
• 인용망 · 지식 그래프: 논문 분야 분류, 개체 관계 추론.
• LLM과의 결합: 문서에서 개체 · 관계 그래프를 뽑아 검색에 쓰는 그래프 RAG (GraphRAG) 는 GNN 학습이 아니라 그래프 구조와 요약을 쓰는 방식이지만, "연결을 따라 정보를 모은다"는 생각을 공유합니다.

연습 문제

1. 노드 4개가 모두 서로 연결된 그래프(완전 그래프)에서 $\tilde d_i$ 와 $\hat A$ 의 모든 원소는?
   • 풀이: 자기 포함 이웃 4개이므로 $\tilde d_i = 4$, 모든 원소가 $1/\sqrt{4\cdot4} = 0.25$ 입니다. 한 층에 모든 노드가 같은 평균값이 됩니다.
2. 본문 그래프에서 $x=(2,2,2)$ 이면 $\hat A x$ 는?
   • 풀이: 노드 1: $2(0.5+0.408) \approx 1.816$, 노드 2: $2(0.408+0.333+0.408)\approx2.299$, 노드 3: 1.816. 값이 같아도 차수에 따라 달라지는 것이 대칭 정규화의 특징입니다.
3. GAT에서 점수 $(0, 0)$ 인 이웃 둘의 가중치는?
   • 풀이: 소프트맥스 결과 $(0.5, 0.5)$ 입니다.
4. GraphSAGE에서 첫 단계 25개, 둘째 단계 10개를 뽑으면 노드 하나 계산에 쓰이는 2단계 이웃은 최대 몇 개인가요?
   • 풀이: $25\times10 = 250$ 개로, 이웃 수와 무관하게 상한이 정해집니다(해설용 설정).

스스로 점검

1. GNN이 이웃 정보를 합 · 평균처럼 모으는 이유는?
   • 답: 이웃에는 정해진 순서가 없으므로, 노드 번호를 바꿔도 같은 결과가 나오도록 순서와 무관한 연산을 써야 하기 때문입니다.
2. GCN에서 $A$ 대신 $A+I$ 를 쓰는 이유는?
   • 답: 셀프 루프가 없으면 새 표현에 자기 자신의 특징이 빠지기 때문입니다.
3. 층을 10개 쌓은 GCN이 2층보다 못할 수 있는 이유는?
   • 답: 이웃 평균을 거듭하면 노드 표현이 서로 비슷해지는 과평활화가 일어나, 노드를 구분할 정보가 사라지기 때문입니다.

용어 정리

더 깊이 보려면

• Distill 「A Gentle Introduction to Graph Neural Networks」 — 대화형 그림과 분자 냄새 예측 놀이터.
• Kipf · Welling GCN 논문 2장 — 스펙트럴 그래프 합성곱에서 전파식이 나오는 유도.
• GraphSAGE 논문 3장 — 집계기 세 가지 비교.
• GAT 논문 2장 — 멀티헤드 어텐션과 귀납 실험(PPI).

다음에 볼 것

• 시계열 예측 기초: 추세 · 계절성 · 자기상관 · 지수평활 · ARIMA · 평가 지표 — 다음 응용 트랙: 시간 순서가 있는 데이터를 예측하고 평가하는 법
• 지역에서 전역으로: 그래프 RAG (GraphRAG) — 그래프 구조를 LLM 검색에 쓰는 방법
• 어텐션만 있으면 된다 (트랜스포머) — 트랜스포머는 '모든 토큰이 연결된 완전 그래프 위의 어텐션 메시지 전달'로 볼 수 있습니다

라이선스

본문은 KAITABASE 자체 해설입니다. 참고 자료 Distill 글은 CC BY 4.0입니다. 3노드 그래프 · 특징 · 가중치 숫자는 이 수업을 위해 만든 해설용 예이며 numpy로 계산을 확인했습니다. 논문 수치는 각 원문에서 확인했습니다.

출처

• Benjamin Sanchez-Lengeling 외, A Gentle Introduction to Graph Neural Networks, Distill, 2021: distill.pub/2021/gnn-intro
• Thomas N. Kipf · Max Welling, Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017: arxiv.org/abs/1609.02907
• Justin Gilmer 외, Neural Message Passing for Quantum Chemistry, ICML 2017: arxiv.org/abs/1704.01212
• William L. Hamilton 외, Inductive Representation Learning on Large Graphs(GraphSAGE), NeurIPS 2017: arxiv.org/abs/1706.02216
• Petar Veličković 외, Graph Attention Networks, ICLR 2018: arxiv.org/abs/1710.10903