CS224W - (10) Knowledge Graph Embeddings
Introduction
지난 번에도 다루었듯 이종 그래프(heterogeneous graph)는 여러 관계 타입을 가진 그래프입니다. 이 그래프를 학습하고 표현하기 위해 관계형 GCN(Relational GCN, RGCN)을 사용했습니다. 이번 포스트에서는 이종 그래프의 일종인 지식 그래프(Knowledge Graphs) 에 대해서 다루도록 하겠습니다.
지식 그래프는 어떠한 지식을 그래프 형태로 나타낸 것으로 노드는 엔티티로 노드 타입으로 레이블되어 있습니다. 엣지는 노드간 관계로 역시 타입이 존재합니다.
Bibliographic Networks
지식 그래프의 예시로 다음과 같은 서지 정보 네트워크를 들 수 있습니다. 논문, 제목, 저자, 컨퍼런스, 발행 연도 등의 노드 타입을 갖고 있고, 어디에 제출했는지, 언제 출판했는지, 제목을 갖고 있는지, 저자가 누군지, 인용이 되었는지 등의 관계 타입을 갖고 있습니다.
Bio Knowledge Graphs
생물학 분야에서도 지식 그래프를 활용할 수 있습니다. 약물, 질병, 부작용, 단백질 등의 노드 타입을 갖고 있고, 처방, 원인 등의 관계 타입을 갖고 있습니다.
이외에도 각 기업에서 지식 그래프를 사용하는 다음의 예시가 있습니다.
- 구글 지식 그래프
- 아마존 제품 그래프
- 페이스북 그래프 API
- IBM 왓슨
- 마이크로소프트 사토리
- 링크드인 지식 그래프
QA와 대화 에이전트에서도 지식 그래프를 활용하기도 합니다.
지식 그래프 완성하기
위 그림처럼 거대한 지식 그래프가 있을 때 이 지식 그래프를 어떻게 완성할 수 있을까요? 주어진 (시작 노드, 관계)가 있을 때 우리는 도착 노드를 예측해야 합니다. 참고로 이 작업은 기존의 링크 예측 태스크하고는 조금 다릅니다. 위 그림과 같이 J.K. Rowling과 장르가 주어졌을 때 도착 노드인 Science Fiction을 찾는게 지식 그래프를 완성하는 일입니다. J.K. Rowling과 Science Fiction은 엔티티가 되고, 두 엔티티간 엣지의 관계 타입은 장르가 됩니다.
지식 그래프의 엣지는 $(h, r, t)$와 같이 트리플렛(triplet)으로 표현됩니다. 우리는 엔티티와 관계를 $\mathbb{R}^d$ 크기의 임베딩으로 모델링하는 것이 목표입니다. 우리는 여기서 GNN을 사용하지 않고 shallow embedding을 이용해 엔티티와 관계를 결합합니다. 실제 트리플렛 $(h, r, t)$가 주어졌을 때 우리의 목표는 $(h, r)$의 임베딩과 $t$의 임베딩이 가까워 지도록 만드는 것입니다. 그러면 다음 두 가지의 질문이 따라오겠죠.
- $(h, r)$은 어떻게 임베딩할 것인가?
- 가까움의 정의는 무엇인가?
이 문제의 답을 구하기 위해 이번 포스트에서는 여러 가지 지식 그래프 임베딩 기법을 다루게 됩니다. 각 기법은 서로 다른 기하학적 직관이나 관계에 대한 표현을 나타내는 방법 등이 다릅니다.
지식 그래프 연결 패턴
이종 지식 그래프의 관계는 여러 가지 특성을 갖고 있습니다.
- 대칭성(Symmetric)
- $r(h, t) \implies r(t, h) \quad \forall h, t$
- 반대칭성(Anti-symmetric)
- $r(h, t) \implies \lnot r(t, h) \quad \forall h, t$
- 역(Inverse)
- $r_2(h, t) \implies r_1(t, h)$
- 전이성(Transitive, Composition)
- $r_1(x, y) \land r_2(y, z) \implies r_3(x, z) \quad \forall x, y, z$
- 일대다(1-to-N)
- $r(h, t_1), r(h, t_2), \cdots, r(h, t_n)$ 이 모두 참
지식 그래프 기법들
TransE
TransE
TransE는 word2vec과 비슷한 느낌입니다. 노드와 관계에 대한 임베딩 벡터 $h, r, t \in \mathbb{R}^d$에 대해서 주어진 정보가 사실이면 $h + r \approx t$이 됩니다. 쉽게 설명하자면 노드 $h$와 노드 $t$의 관계가 만약 $r$이라면 위 그림처럼 $h+r$과 $t$의 위치가 매우 가까워집니다. 반대로 아닌 경우라면 $h + r \neq t$가 되곘죠. 따라서 스코어링 함수는 다음과 같습니다.
\[f_r(h, t) = - \| h + r - t \|\]
Algorithm for learning TransE
TransE를 학습하는 전체 알고리즘은 위와 같습니다. 1번 줄부터 3번 줄까지를 통해 알 수 있듯이 각 엔티티와 관계는 균일하게 정규화하여(uniformly and normalized) 초기화됩니다. 그리고 9번 줄에서 실제 지식 그래프에 존재하지 않는 트리플렛을 샘플링하는 네거티브 샘플링을 수행합니다. 마지막으로 12번 줄에서 다음 수식을 통해 임베딩을 업데이트 하는데요.
\[\sum_{\left( (h, \ell, t), (h^\prime, \ell, t^\prime) \right) \in T_\text{batch}} \nabla [\gamma + d(h + \ell, t) - d(h^\prime + \ell, t^\prime)]_+\]유효한 트리플렛에 대해선 높은 점수를, 네거티브 샘플링된 트리플렛에는 낮은 점수를 주는 대조 손실 함수(contrastive loss) 를 사용합니다. $\gamma$ 뒤의 첫 번째 항이 유효한 트리플렛에 대한 거리(점수의 반대), 두 번째 항이 네거티브 샘플에 대한 거리입니다.
TransE가 지식 그래프의 연결 패턴 중 어떤 것을 만족하는지 알아보도록 하겠습니다.
- 반대칭성 만족
- $h + r = t$이지만 $t + r \neq h$
- 역 만족
- $h + r_2 = t$ 일 때 $r_1 = -r_2$로 설정하면 $t + r_1 = h$을 만족
- 전이성 만족
- $r_3 = r_1 + r_2$ 로 두면 벡터 합에 의해 만족
- 대칭성 불만족
- $r = 0$일 때만 $h = t$를 만족
- 일대다 불만족
- 노드 $h$에서 서로 다른 노드 $t_1, t_2$로 관계가 매핑될 수 없음
- $t_1 = h + r = t_2$ 이지만 $t_1 \neq t_2$ 이므로 모순
TransR
TransR
TransE는 동일한 임베딩 공간에서 모든 관계를 표현하여 다룹니다. 그러면 각 관계에 대해 새로운 임베딩 공간을 설계하고 관계별 공간에서 그래프를 표현할 수 있을까요? TransR은 엔티티를 $\mathbb{R}^d$ 크기의 엔티티 공간으로 모델링하고 각 관계를 관계 공간 $r \in \mathbb{R}^k$으로 모델링합니다. 이에 대한 매핑 행렬로 $M_r \in \mathbb{R}^{k \times d}$을 이용합니다.
엔티티 공간에 두 노드에 대한 임베딩 $h$와 $t$가 있을 때 $h_\perp$와 $t_\perp$가 관계 공간에 임베딩됩니다.
\[h_\perp = M_r h, \qquad t_\perp = M_r t\]이를 이용한 스코어링 함수는 다음과 같습니다.
\[f_r(h, t) = - \| h_\perp + r - t_\perp \|\]TransR은 지식 그래프의 연결 패턴 특징 중 다음을 만족합니다.
- 대칭성 만족
- $| h_\perp + r - t_\perp | = | t_\perp + r - h_\perp |$
- $r = 0$ 일 때 관계 공간에서 $h_\perp$와 $t_\perp$ 는 같은 임베딩이 되는데 이로 인해 $h_\perp = M_rh = M_rt = t_\perp$ 이므로 위 식을 만족함
- 하지만 엔티티 공간에서 $h$와 $t$는 여전히 다른 임베딩을 가짐
- 반대칭성 만족
- $r \neq 0$일 때 $M_rh + r = M_r t$ 이므로 $M_r t + r \neq M_r h$
- 일대다 만족
- $(h, r, t_1)$과 $(h, r, t_2)$가 있다고 가정
- 동일한 관계이므로 $t_\perp = M_r t_1 = M_r t_2$가 되어 일대다를 만족함
- 이때 $t_1$과 $t_2$는 같을 필요가 없음
- 역 만족
- $r_2 = -r_1$, $M_{r_1} = M_{r_2}$
- $M_{r_1} t + r_1 = M_{r_1} h \implies M_{r_2} h + r_2 = M_{r_2} t$
- 전이성 만족
- 행렬 $M$에 대한 커널 공간을 고려해야 함
- $h \in \ker(M) \implies Mh = 0$
- $M_{r_1} g = r_1, M_{r_2} g_2 = r_2$ 로 가정
- $r_1(x, y)$에 대해서 $r_1(x, y)$가 존재하면
- $M_{r_1} x + r_1 = M_{r_1} y \implies y - x \in g_1 + \ker(M_{r_1})$
- 따라서 $y \in x + g_1 + \ker (M_{r_1})$
- $r_2(y, z)$에 대해서도 $r_2(y, z)$가 존재하면
- $M_{r_2} y + r_2 = M_{r_2} z \implies z - y \in g_2 + \ker (M_{r_2})$
- 따라서 $z \in y + g_2 + \ker(M_{r_2})$
- 그러므로 $z \in x + g_1 + g_2 + \ker(M_{r_1}) + \ker(M_{r_2})$
- $\ker(M_{r_3}) = \ker(M_{r_1}) + \ker(M_{r_2})$ 를 만족하는 $M_{r_3}$을 고려할 때
- $\dim(\ker(M_{r_3})) \geq \dim(\ker(M_{r_1}))$ 이고 $M_{r_3}$의 크기는 $M_{r_1}$과 같으므로 $M_{r_3}$이 존재함을 확인할 수 있음
- 강의 슬라이드에 따르면 위 이유로 존재성을 보였지만 두 커널의 선형 결합(linear combination)은 커널이므로 $\ker(M_{r_3}) = \ker(M_{r_1}) + \ker(M_{r_2})$이라고 둘 수 있음
- $r_3 = M_{r_3} (g_1 + g_2)$로 두었을 때 $z - x \in (g_1 + g_2) + \ker(M_{r_3})$
- 따라서 $M_{r_3} x + r_3 = M_{r_3} z$
- 행렬 $M$에 대한 커널 공간을 고려해야 함
DistMult
Score function for DistMult
지금까지 TransE와 TransR의 스코어링 함수는 L1/L2 거리의 음수 형태였습니다. DistMult는 이중선형(bilinear) 모델링을 통해서 지식 그래프를 임베딩합니다. 스코어링 함수의 형태는 $h, r, t \in \mathbb{R}^k$에 대해서 다음과 같습니다.
\[f_r(h, t) = <h, r, t> = \sum_i h_i \cdot r_i \cdot t_i\]
이 스코어링 함수는 $h \cdot r = \sum_i h_i \cdot r_i$과 $t$ 사이의 코사인 유사도로 볼 수 있습니다.
DistMult는 지식 그래프의 연결 패턴 특징 중 다음을 만족합니다.
- 일대다 만족
- $(h, r, t_1)$과 $(h, r, t_2)$가 있을 때 위에서 말했듯이 코사인 유사도로 볼 수 있으므로 $t_1$과 $t_2$가 $h \cdot r$과 각도는 같되 길이가 다른 임베딩이면 되기 때문
- 대칭성 만족
- $f_r(h, t) = <h, r, t> = \sum_i h_i \cdot r_i \cdot t_i = \sum t_i \cdot r_i \cdot h_i = <t, r, h> = f_r(t, h)$
- 반대칭성 불만족
- 위에서 보였듯 항상 $f_r(h, t) = f_r(t, h)$을 만족함
- 역 불만족
- 만약 DistMult가 역을 만족한다면 다음이 성립함
- $f_{r_2}(h, t) = <h, r_2, t> = <t, r_1, h> = f_{r_1}(t, h)$
- 이를 만족하려면 $r_1 = r_2$여야 함
- 전이성 불만족
- 각 관계가 동일한 하나의 초평면(hyperplane)에 표현될 수 없음
ComplEx
Complex conjugate
ComplEx는 DistMult에 기반하여 엔티티와 관계를 복소 벡터 공간(complex vector space) 에 임베딩합니다. 따라서 ComplEx는 엔티티와 관계를 $\mathbb{C}^k$ 위에 모델링합니다. 스코어링 함수는 DistMult와 비슷하지만 복소수의 실수부만 사용합니다.
\[f_r(h, t) = \Re\left(\sum_i h_i \cdot r_i \cdot \bar{t}_i\right)\]이때 $\bar{t}_i$ 는 $t_i$의 켤레 복소수입니다.
ComplEx는 지식 그래프의 연결 패턴 특징 중 다음을 만족합니다.
- 반대칭성 만족
- $f_r(h, t) = \Re \left( \sum_i h_i \cdot r_i \cdot \bar{t}_i \right)$
- $f_r(t, h) = \Re \left( \sum_i t_i \cdot r_i \cdot \bar{h}_i \right)$
- 켤레 복소수로 인해 두 식은 다르게 됨
- 대칭성 만족
- $\Im(r) = 0$이라고 가정할 때
- $f_r(h, t) = \Re(\sum_i h_i \cdot r_i \cdot \bar{t}_i) = \sum_i \Re(r_i \cdot h_i \cdot \bar{t}_i) = \sum_i r_i \cdot \Re(h_i \cdot \bar{t}_i)$
- 같은 엔티티 공간 내에서 켤레 복소수의 순서를 바꾸는 것은 문제가 되지 않음
- $\sum_i r_i \cdot \Re(h_i \cdot \bar{t}_i) = \sum_i r_i \cdot \Re(\bar{h}_i \cdot t_i) = \sum_i \Re(r_i \cdot \bar{h_i} \cdot t_i) = f_r(t, h)$
- 역 만족
- $r_1 = \bar{r}_2$
- $r_2 = \arg\max_r \Re(<h, r, \bar{t}>) = \arg\max_r \Re(<t, r, \bar{h}>) = r_1$
- 전이성 불만족 / 일대다 만족
- DistMult의 특성을 고스란히 이어 받음
실제 사용할 때는
서로 다른 지식 그래프는 관계 패턴이 크게 다를 수 있습니다. 따라서 모든 지식 그래프에 적용되는 일반적인 임베딩은 없습니다. 따라서 지금까지 다룬 모델들 중 적절한 모델을 적용해야 합니다. 만약 지식 그래프가 대칭 관계가 많지 않은 경우 빠른 프로토타이핑을 위해 TransE를 사용해보는 것도 좋습니다. 아니면 보다 표현력 있는 모델이 필요하다면 ComplEx나 TransE의 복소 공간 버전인 RotatE를 사용해보는 것도 좋습니다.