이번 강의 한 줄 요약:
노드 임베딩을 “외워서 저장(lookup)”하던 시대(DeepWalk/node2vec)에서,
“이웃 정보를 모아 계산하는” 딥러닝 방식(GCN/GraphSAGE)으로 넘어간다.
목차
- 지금까지의 노드 임베딩: Encoder–Decoder 관점
- Shallow encoding(DeepWalk/node2vec)의 한계
- 왜 그래프는 그냥 MLP/CNN으로 못 푸나?
- GNN 핵심 아이디어: Neighborhood Aggregation(이웃 집계)
- Deep Graph Encoder 수식 직관 (왜 이웃항 + 자기항을 섞나)
- 파라미터 공유와 Inductive capability(새 노드/새 그래프 일반화)
- Graph Convolutional Network(GCN) vs GraphSAGE
- GraphSAGE의 AGG(집계 함수) 변형들: mean/pool/LSTM
- 오늘 강의 최종 요약 + 자가체크 질문
1) 지금까지의 노드 임베딩: Encoder–Decoder 관점
우리가 계속 하던 건 이런 느낌이었다.
- 입력: 그래프 G
- 출력: 각 노드의 임베딩 zv∈Rd
- 목표: 그래프에서 “비슷한 노드”는 임베딩 공간에서도 “가깝게”
이를 프레임워크로 보면:
- Encoder: 노드 v↦zv (임베딩을 만드는 쪽)
- Decoder: 두 임베딩의 유사도(예: dot product)로 그래프의 유사도 재현
2) Shallow encoding(DeepWalk/node2vec)의 한계
DeepWalk/node2vec는 사실상 “임베딩을 외워서 저장”하는 구조였다,
- 임베딩 행렬 Z∈Rd×∣V∣를 직접 학습
- 노드 임베딩은 그냥 lookup: “v에 해당하는 열을 꺼낸다”
단점 4가지 (시험/면접 단골)
- 파라미터 수 폭발: |V| 커지면 d×∣V∣ 그대로 커짐
- 파라미터 공유 없음: 노드마다 따로 외움
- Transductive: 학습에 없던 새 노드/새 그래프에 약함
- 노드 피처 반영이 약함: feature 기반으로 “계산해서” 임베딩을 만들기 어려움
➡️ 그래서 등장: Deep Graph Encoder = GNN
3) 왜 그래프는 그냥 MLP/CNN으로 못 푸나?
“인접행렬 A + 특성 X를 합쳐서 신경망에 넣으면 되지 않나?”
처음엔 다 그렇게 생각하는데, 그래프는 여기서 막힌다.
(1) 그래프 크기가 가변
노드 수가 바뀌면 인접행렬 크기부터 달라져서 입력 형태가 고정되지 않는다.
(2) 노드 순서(permutation)에 민감
같은 그래프라도 노드 번호만 바꾸면 인접행렬은 행/열이 섞여서(permute) 완전히 다른 입력처럼 보인다.
그래프에는 이미지처럼 “좌상단 픽셀” 같은 기준점이 없기때문,,
(3) CNN처럼 고정 창(window)이 없다
이미지는 3×3 커널처럼 “항상 같은 모양의 이웃”이 있는데,
그래프는 어떤 노드는 이웃이 3개, 어떤 노드는 300개… 고정된 창이 애매하다.
결론: 그래프에서는 순서에 불변(permutation invariant)인 방식으로 이웃 정보를 모아야 한다.
4) GNN 핵심 아이디어: Neighborhood Aggregation(이웃 집계)
CNN에서 “중심 픽셀이 주변 픽셀을 모아 업데이트”하듯이,
GNN에서는
중심 노드가 이웃 노드들의 정보를 모아서(aggregate) 자기 표현을 업데이트한다.
- 0층(입력):
- 그 다음 층들: “이웃 → 집계 → 결합 → 비선형 변환”
그리고 층을 개 쌓으면
K-hop까지의 정보가 반영된다.
5) Deep Graph Encoder 수식 직관 (왜 이웃항 + 자기항을 섞나)
강의 슬라이드에서 본 기본 형태는 이런 느낌이었다:
여기서 제일 중요한 질문이 나옵니다.
“왜 이웃항과 자기항을 굳이 둘 다 넣어서 선형결합하지?”
핵심은 딱 두 가지이다.
- 이웃항(이웃 평균): “주변 컨텍스트”를 가져오기
- 자기항(self): “내 정체성”을 유지하기
자기항이 없으면 업데이트가 이웃에만 끌려가서 나 자신 정보가 빨리 희석된다.
반대로 이웃항이 없으면 그래프 구조를 쓰는 의미가 약해진다.
즉, (나) + (내 주변) 을 섞어서 다음 표현을 만드는 게 GNN의 기본 뼈대이다.
6) 파라미터 공유와 Inductive capability(새 노드/새 그래프 일반화)
여기서 많은 사람들이 한 번 더 걸린다.
Q. “그러면 W, B는 노드마다 다른가?”
아니요.
같은 레이어 l에서는 모든 노드가 동일한 W_l, B_l를 공유한다.
(레이어가 바뀌면 Wl+1,Bl+1로 달라짐)
Q. “노드마다 다르게 두는 게 더 최적 아닌가?”
노드마다 W를 두면 → 파라미터가 노드 수에 비례해서 폭발 → 결국 shallow처럼 “외우는 모델”로 회귀한다.
파라미터 공유는 이런 장점이 있다.
- 규모 확장: 노드 수가 커져도 파라미터가 같이 커지지 않음
- 일반화: “이웃을 모아 업데이트하는 규칙”을 학습하므로
학습에 없던 노드에도 적용 가능
그래서 GNN의 중요한 특성이:
Inductive capability
- New graphs: 한 그래프에서 학습 → 다른 그래프에도 적용
- New nodes: 스냅샷으로 학습 → 새 노드 들어오면 forward만으로 임베딩 생성(“on the fly”)
7) GCN vs GraphSAGE: 차이는 “집계(AGG)를 얼마나 일반화하냐”
GCN(기본형)
- 이웃을 평균(mean)으로 집계하는 방식이 대표적
GraphSAGE
- “이웃 평균”을 딱 하나로 고정하지 않고,
- AGG(집합 → 벡터) 함수로 일반화한다.
여기서 포인트:
- 이웃은 순서 없는 집합(set) → AGG는 기본적으로 순열 불변이어야 함
8) GraphSAGE의 AGG 변형들: mean / pool / LSTM
강의에서 대표로 소개된 변형 3가지:
(1) Mean aggregator
- 가장 안정적인 기본기
- 이웃 평균(또는 가중 평균)
(2) Pool aggregator
- 이웃마다 MLP로 변환해준 뒤
- element-wise max/mean 같은 pooling
직관:
“이웃들의 특징 중에서 중요한 신호를 ‘뽑아내는’ 느낌”이 강해짐
(3) LSTM aggregator
- 이웃들을 섞어서 sequence처럼 넣고 LSTM으로 집계
- 표현력은 좋을 수 있는데, set을 sequence로 다룬다는 점에서 설계상 논의 포인트가 있음(그래도 아이디어는 “더 강한 집계”)
9) 오늘 강의 요약
- Shallow embedding은 노드별 임베딩을 외움 → 새 노드/새 그래프에 취약
- GNN은 이웃을 집계해서 임베딩을 ‘계산’함
- 중요한 제약: 노드 순서에 불변(permutation invariant)이어야 함
- 기본 수식은 “이웃 정보 + 자기 정보”를 섞고 비선형 변환
- 파라미터(Wl,BlW_l,B_l)는 같은 레이어에서 모든 노드가 공유
- 그래서 Inductive가 가능: 새 노드/새 그래프에도 forward로 임베딩 생성
- GraphSAGE는 집계(AGG)를 일반화해서 mean/pool/LSTM 등으로 확장