(R-GCN + KG Embedding + Negative Sampling + Hits@K/MRR)
9강에서 “GNN이 무엇을 구분할 수 있나(표현력)”를 이론으로 봤다면, 10강은 다시 응용으로 돌아오되 그래프가 더 현실적으로 복잡해지는 순간을 다룬다.
바로 이종 그래프(heterogeneous graph), 그리고 그 대표 사례인 지식 그래프(Knowledge Graph, KG)다.
0) 왜 10강이 중요한가?
지금까지는 “노드 타입 1개 + 엣지 타입 1개”인 단순 그래프만 다뤘다.
하지만 현실 데이터는 대부분 이렇다:
- 노드 타입이 여러 개 (사람/회사/질병/약물/논문/저자/학회…)
- 관계(엣지) 타입도 여러 개 (treats, causes, cites, works_at, located_in…)
즉 그래프의 한 엣지는 이제 그냥 (i, j)가 아니라
(head, relation, tail) = (i, r, j)
라는 삼중항(triple)로 봐야 한다.
이 구조를 처리하는 게 10강의 목표.
1) Heterogeneous Graph란?
이종 그래프는 “서로 다른 종류의 엔티티 + 서로 다른 종류의 관계”를 포함한다.
- 노드 집합 V: 노드마다 타입이 존재
- 관계 집합 R: 엣지마다 관계 타입이 존재
- 각 엣지: (i,r,j)
예시 1) 바이오메디컬 그래프
- 노드 타입: disease / drug / protein
- 관계 타입: treats / interacts / causes / associated_with …
“약물이 질병을 치료(treats)한다”와 “단백질-단백질 상호작용(interacts)”은 의미가 완전히 다르다.
모델이 이 차이를 파라미터로 구분해서 학습해야 한다.
2) 그래서 R-GCN(Relational GCN)이 필요하다
기존 GCN은 “모든 엣지에 같은 변환 행렬 W”를 적용했다.
이종 그래프에서는 그게 말이 안 된다.
관계 타입이 다르면 메시지의 의미도 다르니, 관계별 변환 Wr를 따로 두자.
방향 그래프(directed)일 때 메시지 패싱 복습
방향이 있으면 보통 “들어오는(incoming) 이웃”에서만 메시지를 받는다고 생각하면 된다.
계산 그래프(computation graph)도 엣지 방향을 따라 펼쳐진다.
3) R-GCN 업데이트 식: “관계별로 모아서, 관계별로 변환”
노드 vv의 다음 레이어 임베딩은
- 관계 타입 마다
- 로 v에 연결된 이웃들만 모아서
- 그 관계 전용 행렬 Wr로 변환 후
- 다 합친다 (정규화 포함)
핵심 해석:
- 변환(transform): 관계별 Wr
- 집계(aggregate): sum (+ normalization)
여기서 Cv,r는 보통 “relation r의 in-degree” 같은 정규화 상수 역할.
4) R-GCN의 치명적인 문제: 관계가 많으면 파라미터 폭발
각 레이어마다 관계별 행렬이 필요하다:
- 레이어가 L개
- 관계 타입이 |R|개
- 각 Wr(l)는 대략 d×d
그러면 파라미터 수가 L × |R| × d² 수준으로 터진다.
지식 그래프는 관계 타입이 수백~수천, 심하면 수만 개다.
(Freebase 같은 애들은 relation type이 말도 안 되게 많음)
그래서 10강은 “관계가 많을 때 어떻게 줄이냐”가 핵심 트릭이다.
5) 파라미터 줄이기 1: Block Diagonal (희소하게 만들기)
Wr를 “블록 대각” 구조로 제한한다.
- 큰 행렬을 B개 블록으로 쪼개고
- 블록 밖은 0으로 둠
장점:
- 파라미터 대폭 감소
- 학습 안정 / 과적합 완화
단점:
- 서로 다른 블록 차원끼리 한 번에 상호작용 불가
(표현력은 조금 제한될 수 있음)
6) 파라미터 줄이기 2: Basis / Dictionary Decomposition (가중치 공유)
관계마다 행렬을 “독립적으로” 두지 말고,
소수의 기저 행렬(basis)들의 선형 결합으로 표현한다.
- Vb: 기저 행렬(딕셔너리) B개만 학습
- ar,b: 관계 r의 결합 계수(스칼라)만 학습
관계가 1000개여도 B=10이면
각 관계는 “10개 숫자”만 가지면 된다.
=> 관계 수가 커질수록 이 방식이 압도적으로 유리
7) 이종 그래프에서의 태스크 정의
(1) 노드/엔티티 분류
- R-GCN으로 임베딩 만들고
- 기존처럼 분류 헤드(선형+softmax 등) 얹으면 끝
(2) 링크 예측(link prediction) — 관계 타입이 있으니 더 까다롭다
관계 타입별로 데이터 분할이 불균형해질 수 있다.
- 흔한 관계: 엣지 많음
- 희귀 관계: 엣지 거의 없음 → val/test에 아예 안 들어갈 수도
그래서 해야 할 것:
관계 타입별로 stratified split(층화 분할)하고 합치기
그리고 링크 예측은 8강에서 봤듯 엣지가 2역할이라 더 복잡해진다.
- message passing edges (임베딩 만들 때 쓰는 엣지)
- supervision edges (손실 계산용 정답 엣지)
관계 타입까지 있으니 “relation별로 이 구조를 관리”해야 한다.
8) Knowledge Graph(KG): 이종 그래프의 대표 선수
지식 그래프는 “도메인 지식”을 그래프에 저장한다.
- 노드: 엔티티(entity)
- 엣지: 관계(relation)
- 타입: 엔티티 타입/관계 타입
예시: 서지 네트워크(논문 그래프)
- 엔티티: paper / author / conference / year / title …
- 관계: written_by, published_in, cites, has_year …
예시: 바이오 지식 그래프
- drug / disease / protein / adverse_event …
- treats, causes, associated_with, has_function …
현업에서도 KG는 흔하다:
검색/추천/QA/에이전트에서 “구조화된 지식”이 필수라서.
9) KG Completion: “비어 있는 사실(엣지)을 채워라”
KG의 특징:
- 엄청 크다
- 그리고 엄청 불완전하다(incomplete)
즉 우리가 하고 싶은 일:
(h, r, ?) 또는 (?, r, t)
같은 쿼리에서 빠진 엔티티를 맞히거나,
“이 triple이 사실인가?”를 판단하는 것
이게 Knowledge Graph Completion.
10) KG 링크 예측: 스코어링(Scoring) 함수가 핵심
R-GCN으로 각 엔티티 임베딩 hvh_v를 만든 뒤,
관계 타입 r에 대해 “이 triple이 맞는지” 점수를 계산한다.
강의에서 대표로 든 형태가 bilinear score:
- head 임베딩을 관계 행렬로 변환한 뒤
- tail과 내적
여기에 sigmoid를 붙이면 “존재 확률”처럼 해석 가능.
11) Negative Sampling: “가짜 엣지”를 만들어 학습시킨다
링크 예측은 양성 엣지만으로 학습이 어렵다.
그래서 negative edges를 만든다.
방법: positive triple을 corrupt 한다.
- (E, r3, A)가 양성이면
- tail을 바꿔서 (E, r3, B), (E, r3, D) 같은 음성을 만든다
(혹은 head를 바꾸기도 함)
주의:
- 만든 음성이 실제로 그래프에 존재하면 안 됨
- message edges / supervision edges에 이미 있는 엣지도 안 됨
12) Loss: “양성 점수 ↑, 음성 점수 ↓”
가장 표준적인 목표:
- positive triple의 score는 크게
- negative triple의 score는 작게
로지스틱/크로스엔트로피 기반으로 학습하면 된다.
13) 평가: Hits@K, MRR이 표준
KG completion은 보통 “랭킹 문제”로 평가한다.
- 특정 (h, r, ?) 쿼리에서 후보 엔티티들을 점수로 정렬
- 정답 tail이 몇 등인지 본다
지표:
- Hits@K: 정답이 상위 K 안에 들면 성공
- RR(Reciprocal Rank): 1/rank1 / rank
- MRR: RR 평균
MRR이 높을수록 “정답을 위에 랭킹하는” 모델이다.
14) 요약
이종 그래프에서는 “관계 타입이 메시지 의미를 바꾼다” → 관계별 파라미터가 필요하고,
관계가 많아지면 파라미터가 폭발하니 Block diagonal / Basis decomposition으로 줄인다.
지식 그래프 완성은 (h, r, t) triple을 스코어링 + negative sampling + Hits/MRR로 푸는 랭킹 문제다.