Knowledge Graph Embedding 정리

Knowledge Graph Embedding

Knowledge Graph Embedding은 Knowledge Graph(이하 KG) 구성요소들, 그러니까 entity(node)와 relation(edge)을 벡터공간에 임베딩하는 방법이다. 물론, entity와 relation을 벡터공간에 임베딩할 때는 그냥 정규분포, 가우시안분포로부터 임의로 임베딩 벡터를 생성할 수도 있다. 하지만 NLP에서 주변 단어를 활용하는 word2vec과 같은 단어 임베딩 방법들이 존재하는 것처럼, KG가 가지고 있는 구조 정보를 활용한다면 더 성능이 좋은 임베딩 벡터를 만들어낼 수 있다.

즉, Knowledge Graph Embedding(이하 KGE)은 KG의 구조정보를 잘 유지한 채 KG의 구성요소들을 임베딩 벡터 공간에 매핑하는 것을 목표로한다. 그렇다면 KGE라는 것 자체가 왜 필요할까를 생각해보자. 딥러닝, 머신러닝 기반의 모델들은 입력을 그대로 이용하기 보다는 그 representation을 주로 사용한다. CNN 모델이 사진을 3차원 텐서로 변환한다던지, NLP 모델이 문장을 벡터로 변환하는 것처럼 말이다. 따라서, KG의 풍부한 표현력을 필요로하는 많은 downstream task, 예컨대 recommender system이나 question answer system, 들에서 KG를 이용하고자 한다면 이 구성요소들을 임베딩할 필요가 생기는 것이다.

혹시 KG embedding에서 사용되는 KG를 잘 모르는 사람들을 위해 짧게 써보자면, 모든 Knowledge Graph는 트리플(h,r,t)로 이루어져있다. 각 트리플을 구성하는 것은 ‘Head Entity’, ‘Relation’, ‘Tail Entity’이다. 예를 들면, (봉준호, directorOf, 기생충)은 하나의 트리플을 구성하며 Head Entity(봉준호), Tail Entity(기생충), Relation(directorOf)을 이룬다. KG 상에서는 두 개의 node와 그 사이의 edge로 표현된다. 앞으로 나오는 head, tail과 같은 표현은 위의 요소들을 설명하는 것이다.

어쨋든 오늘은 KGE와 관련된 서베이 논문을 읽고 내용을 정리해보고자 한다. 하지만, 이 글의 목적은 ‘이렇게나 많은 방법들을 정리한다’가 아니라 ‘앞으로 어떤 KGE 방법이 나와도 이해할 수 있게 한다’이다.

KGE를 이해하기 위한 요소

먼저, 앞으로 나올 다양한 KGE 방법들을 쉽게 이해하기 위해서는 총 3가지 요소에 집중해야한다.

1. Representation of entities and relations
2. Scoring function
3. Learning method

1번, entity와 relation을 어떻게 ‘표현’했는가이다. 각각의 KGE 모델들은 그들만의 entity, relation representation을 갖는다. 어떤 모델은 entity를 vector로 relation을 matrix로 표현할 수도 있고, 또 다른 모델은 entity와 relation 모두를 vector로 표현할 수도 있다. 따라서 각 모델별로 이 KG의 구성요소들을 어떻게 표현했는지 알아야한다.

2번, score function의 차이를 잘 알아야한다. 당연하지만 이 score는 loss와는 음의 상관관계를 가질 것이고, KGE 모델 학습의 원동력이 된다. 어떤 entity끼리 서로 뭉칠지, 혹은 멀어질지 등은 이 score function으로부터 정의될 것이다. 앞으로 KGE 모델을 크게 두 가지 줄기로 분류할텐데, 이 때도 어떤 종류의 score function을 사용했는가를 기준으로 구분하게될 예정이다.

3번, 사실 모델 학습은 다른 딥러닝 모델들과 다를 바가 없다. loss를 정하고(물론 score를 이용해서), optimizer를 선택한 뒤에 학습시키면 된다. 하지만, word2vec 같은 방법과 동일하게 negative sampling하는 과정이 필요하고 이는 추후 한 번에 설명하도록 하겠다.

앞으로 다양한 KGE 모델들을 살펴볼텐데, 이 모델들이 어떻게 ‘entity와 relation을 표현했는지’와 ‘어떤 score function을 정의했는지’를 기준으로 분석해보자.

Translation Distance Method

Translation Distance Method 기반의 KGE 모델들은 ‘distnace-based scoring function’을 사용한다. 대부분의 KGE 모델들은 relation을 하나의 ‘operation’으로 생각하는데, 이 Translation Distance Method 기반의 모델들은 entity vector를 relation을 이용해 ‘translation’한 뒤에 entity들 사이의 ‘거리’를 score function에 사용한다.

TransE

TransE는 가장 기본적이면서 대표적인 Translation Distance Method 기반의 KGE 모델이다. Head entity 벡터와 Relation 벡터를 더했을 때(operation)의 벡터와 Tail entity 벡터 사이의 거리를 최소화하는 것을 목표로 한다. 즉, ‘봉준호’ entity 벡터와 ‘directorOf’ relation 벡터를 더한 결과가 ‘기생충’ entity 벡터에 가깝게 가고자 하는 것이다. 이전에 예고한대로 모델들의 표현과 score function을 정리해보자.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation 또한 같은 공간의 d차원의 벡터로 표현했다.

Score function

\[f_r(h, t) = -||h+r-t||_{1/2}\]

그런데 왜 마이너스가 붙어있을까? 생각해보면, 위 식은 ‘score’이다. 따라서, h + r 과 t 차이가 크면 클수록 score가 낮아져야하기 때문에 앞에 음의 부호를 붙인 것이다.

---

TransH

TrasnE는 간단하면서 직관적인 모델이지만, 부족한 부분이 있다. 바로 1-N, N-1 등의 관계에 취약하다는 것이다. 봉준호 감독은 기생충이라는 영화를 하나만 만들지 않았다. 이를 트리플로 표현해보자면, (봉준호, directorOf, 기생충), (봉준호, directorOf, 설국열차) 등이 있을 것이다. 하지만 TransE로 학습을 하게 되면 결국에는 기생충과 설국열차 entity 벡터가 비슷한 공간에 위치하게 된다. 이는 TransE가 1-1 관계만 표현할 수 있는 모델이기 때문이다. 위 문제를 극복하기 위한 모델이 바로 TransH이다.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation 또한 같은 공간의 d차원의 벡터로 표현했다. 추가적으로 Relation은 d차원의 normal 벡터를 갖는다.

Score function

\[h_{\bot} = h - w^{\top}_{r}hw_{r}\] \[t_{\bot} = t - w^{\top}_{r}tw_{r}\] \[f_r(h, t) = -||h_{\bot}+r-t_{\bot}||^{2}_{2}\]

각 relation은 저마다의 hyperplane을 가지며, head, tail entity를 그 hyperplane에 projection 시킨 뒤 relation vector를 이용하여 거리의 차를 계산하게 된다. 이렇게 하면, 같은 tail entity (예시에서 기생충, 설국열차) 들이 다른 값의 벡터를 가지고 있더라도, 특정 relation (예시에서 directorOf) 에 한해서는 비슷한 representation을 또는 아주 다른 representation을 얻게할 수 있다.

---

TransR

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation은 k차원의 벡터로 표현했다. Relation은 d x k 크기의 matrix를 갖는다.

Score function

\[h_{\bot} = M_{r}h\] \[t_{\bot} = M_{r}t\] \[f_r(h, t) = -||h_{\bot}+r-t_{\bot}||^{2}_{2}\]

TransR은 TransH와 비슷한 아이디어지만 hyperplane 대신 relation-specific space가 있어 relation에 따라 entity들이 relation space에 대응되도록 하였다. 하지만 TransR은 풍부한 relation 표현력을 얻었으나 relation별로 d x k 크기의 projection matrix가 필요한 만큼 많은 parameter 수를 차지하여 relation 개수가 많은 경우 사용하기 힘들 수 있다.

---

KG2E

지금까지 살펴본 방법들은 entity와 relation을 벡터 공간상의 하나의 벡터 (deterministic point)로 표현하였다. 하지만 꼭 이렇게 표현해야한다는 의미는 아니다. KG2E모델은 여기에 불확실성이라는 개념을 반영하여 entity와 relation을 확률변수로 두고 표현하기도 한다.

Entity/Relation 표현

$ h \sim \mathcal{N}(\mu_h, \sum_h) $

$ t \sim \mathcal{N}(\mu_t, \sum_t) $

$ r \sim \mathcal{N}(\mu_r, \sum_r) $

Score function

KL divergence, Probability inner product 와 같은 확률변수 사이의 거리를 측정하는 방식을 이용해서 정의한다.

---

Others

이 뿐만 아니라 Translation Distance Method에는 TransA, TransF, TransG 등 수많은 방법들이 존재한다. 하지만 기억해야할 것은 각 모델들은 ‘각자가 중요하게 생각하는 문제’를 해결하기 위한 새로운 representation, 새로운 score function을 제시한 것 뿐이라는 것이다.

Semantic Matching Method

Semantic Matching Method에 속하는 KGE 모델들은 앞서 살펴본 Translation Distance Method와 달리 score를 정의하는 데 있어 ‘Similarity’를 중요하게 생각한다. ‘Distance’가 아닌 ‘Similarity’이다.

RESCAL

Semantic Matching Model에서 TransE와 같은 든든한 기반이 되는 모델은 RESCAL이다. 각 relation은 head와 tail entity의 latent factors의 pairwise interaction을 의미한다고 볼 수 있다.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation은 d x d 매트릭스로 표현했다.

Score function

\[f_r(h, t) = h^{\top}M_rt = \sum\limits^{d-1}_{i=0}\sum\limits^{d-1}_{j=0}[M_r]_{ij}\cdot[h]_i\cdot[t]_j\]

---

DistMult

DistMult는 RESCAL의 복잡성을 지적하면서 등장한 모델이다. 기존 RESCAL에서 Relation이 d x d 매트릭스이다보니 parameter 갯수가 많다는 단점을 극복하기 위하여 d차원 벡터로 변형하였다.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation 또한 같은 공간의 d차원의 벡터로 표현했다. 다만, relation 벡터를 diagonal 매트릭스에 삽입하였다.

Score function

\[f_r(h, t) = h^{\top}diag(r)t = \sum\limits^{d-1}_{i=0}[r]_{i}\cdot[h]_i\cdot[t]_i\]

---

HolE

HolE(Holographic Embeddings)는 RESCAL의 표현력과 DistMult의 simplicity를 결합한 모델이다. Circular correlation operation을 도입하였다.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation 또한 d차원의 벡터로 표현했다.

Score function

\[[h{\star}t]_i = \sum\limits^{d-1}_{k=0}[h]_k\cdot[t]_{(k+i)\mod d}\] \[f_r(h, t) = r^\top (h\star t)\]

---

MLP

Neural Network 구조를 이용한 semantic matching 모델들도 존재한다. h, r, t를 input layer를 통해 embedding 시킨 뒤, weight와 bias 등을 이용해 신경망 구조를 거쳐 output을 내는 방식이다. 가장 흔히 사용되는 Multi-layer perceptron을 이용한 경우는 아래와 같다.

Entity/Relation 표현

Entity는 d차원의 벡터로, Relation 또한 같은 공간의 d차원의 벡터로 표현했다. 첫 번째 레이어에 M1,M2,M3 각 d x d 차원 weights와 두 번째 레이어에 w d차원 weight가 존재한다.

Score function

\[f_r(h, t) = w^\top \tanh(M^1h+M^2r+M^3t)\]

---

NTN

Neural Tensor Network는 Relation에 3차원 Tensor를 이용하기도 하였다. Relation을 가장 expressive하게 표현한 모델이지만, 당연하게도 parameter를 많이 필요하게 된다.

Entity/Relation 표현

Entity는 d차원의 벡터로 표현했다. Relation은 k차원 벡터 1개, dxk 차원의 매트릭스 2개, dxdxk 차원의 텐서 1개로 표현했다.

Score function

\[f_r(h, t) = r^\top \tanh(h^\top \underline{M}_rt + M^1_rh + M^2_rt + b_r)\]

다시 한 번 마지막으로 언급하지만, 이 포스트의 목적은 모든 임베딩 방법들에 deep dive를 하는 것이 아니다. 각 모델이 ‘각자의 사정’으로 ‘각자의 entity, relation representation’을 가지며, ‘각자의 score function’을 갖는다는 것을 이해하고자 함이다.

Model Training

이제 KGE모델을 학습시켜야한다. 학습을 위해서는 KG로부터 트리플을 추출하여, 실제로 KG에 존재하는 트리플(fact)이라면 score를 높게 학습시키고, 존재하지 않는 트리플이라면 score를 낮게 학습시켜야한다. 그런데 문제가 하나 있다. 바로 label이 0인 Negative sample을 생성해야한다는 것이다. KG안에서 관측되는 트리플을 label 1인 sample로 만드는 것은 그냥 추출이니까 쉽다. 그렇다면 label이 0인 negative sample은 어떻게 추출해야할까?

간단한 방법으로는 관측된 트리플 (h,r,t)로부터 h, t 혹은 r을 다른 값으로 교체하는 것이다. (봉준호, directorOf, 기생충) 에서 기생충을 ‘바스터즈: 거친녀석들’로 바꾸게되면 이는 label이 0인 negative sample이 된다.

하지만 이 방법에 문제가 있는데, 바로 이런식으로 manipulation을 가한 트리플이 사실 fact가 될 수 있다는 점이다. (봉준호, directorOf, 기생충)를 (봉준호, directorOf, 마더)로 바꿨다고 해보자. 이 때는 negative sample을 추출하기 위한 과정에서 positive sample을 만들어버릴 수도 있게 된다.

따라서 참고할 수 있는 방법으로 1-N관계의 1쪽을 변경하는 것이다. 1-N관계라는 것 자체가 단 한 종류의 값만 가질 수 있다는 것을 의미하기 때문이다. (봉준호, genderOf, 남자)를 예로 들면, 이를 (봉준호, genderOf, 여자)로 바꾸는 것이다. 성별은 하나만 가질 수 있는 1-N에서 1쪽의 relation이기 때문이다.

여차저차 positive sample과 negative sample을 구했다고 한다면, 우리는 KGE 학습을 위한 두 가지의 Loss function을 생각해볼 수 있다.

첫 번째 Loss는 Logistic Loss이다.

이 Loss function은 Positive sample을 1, Negative sample을 0으로 두고 KGE 학습을 ‘classification’문제로 분류한 것이다.

두 번째 Loss는 Pairwise Ranking Loss이다.

이 Loss function은 Negative sample (Unseen Triple) 을 반드시 flase(0)라고 생각하지 않고, 단지 Positive sample보다는 score가 낮도록(Invalid하다고) 학습하는 방법이다. 실제 KG는 사람들이 구축한 것이기 때문에 완벽할 수 없다. 예컨대, User Entity와 Movie Entity사이에 Watch Relation을 추가하여 시청기록을 관리한다고 해보자. 이 때 어떤 User가 어떤 Movie와 연결되지 않았다는 사실만으로 그 User가 해당 Movie를 싫어한다고(Negative, 0) 단정지을 수 없다. 단지, 이미 본 기록이 있다면(Positive) 안 본 것보다는 낫다고 판단할 수 있을 뿐이다.

결과적으로 KGE 모델의 학습을 수도코드로 나타내면 아래와 같다.

Positive Sample에 대응하는 Negative Sample을 구하고, 정해진 Score에 따른 Loss를 최소하는 방향으로 학습하는 것이다.

Downstream task

이렇게 학습된 KG Embedding들은 여러 가지 Downstream task에서 사용될 수 있다.

제일 먼저 KG 자체에서 활용하는 방법은 Link Prediction이다.

Link prediction은 KG 내에 구성되지 않은 Link를 찾아내는 task이다. 때에 따라 Missing Entity를 찾는 것도 Link prediction이라고 불리기도 한다. 우리가 TransE를 통해 KG Embedding을 학습했다고 가정하자. 만일 (봉준호, ?, 기생충) 이라는 트리플에 대해 Relation이 존재하지 않을 때, 어떻게 이 Missing Link를 구할 수 있을까? TransE는 h + r = t 를 목표로 학습되기 때문에, r = t - h를 유도할 수 있고 따라서 ‘기생충’ 벡터에서 ‘봉준호’ 벡터를 뺀 뒤 가장 비슷한 벡터를 가진 relation 벡터를 나열하면 된다. 잘 학습된 TransE 모델이라고 한다면 제일 처음에 ‘directorOf’ relation이 랭킹될 것이다.

단순히 KG 안의 문제를 해결하는 것 뿐만 아니라 KG를 이용하는 거의 모든 딥러닝/머신러닝 방법에도 적용될 수 있다. NLP에서 감정분류를 위한 LSTM 모델을 만들고 word2vec으로 학습된 단어 임베딩을 사용하는 것처럼, KG를 이용한 QA모델 또는 추천모델에서 KG component의 임베딩을 KGE로 학습된 값을 이용하는 것이다. KGE 모델은 KG 구조에 대한 정보를 충분히 학습했기 때문에 단순한 Randomly initialized된 임베딩보다 효과적인 성능을 가져다줄 수 있을 것이다.

뿐만 아니라, Multi-task learning으로도 활용할 수 있다. 예컨데, KG를 이용한 QA모델이라고 한다면 QA Loss 뿐만 아니라 KGE Loss를 함께 사용한다던가, KG를 이용한 추천모델이라고 한다면 추천 Loss 뿐만 아니라 KGE Loss를 함께 사용하여 학습하는 것이다.

QA모델 중 DRAGON은 Pre-training 과정에서 Language Model과 KGE모델을 동시에 학습시키는 Joint learning을 진행했다. LM은 Masked language model로, KGE는 Link prediction을 Loss로 하여 이 두 Loss를 합쳐 동시에 학습을 했고 KGE 학습을 추가하여 1.7%p~5%p의 성능 향상을 이루어내었다. 추천모델 중 KGAT은 KG를 활용하였으며 기존 Collaborative Filtering Loss에 KGE Link prediction Loss를 추가하여 성능 향상을 이룬 바가 있다.

정리

짧게 정리해보자면, KGE는 KG 구조 정보를 유지한 채 구성요소인 Entity와 Relation을 학습하는 것이다. 각 KGE 모델은 각자의 entity/relation representation과 score function을 갖는다. Score function을 기반으로 하여 학습된 KG Embedding 값은 다른 Task의 Initial 값으로도 쓰일 수 있다. 뿐만 아니라 Multi-task learning으로 주된 Loss에 더해져 동시에 학습되기도 하고 성능이 높아지는 결과를 가져온다.

KGE를 쓸 수 있는 오픈소스는 OpenKE가 있다.

이 오픈소스 결과에서 확인할 수 있듯 꼭 복잡한 모델이라고 좋은 성능을 내는 것은 아니다. 공부할 때 무조건 TransR이나 TransH가 TransE보다 좋을 것 같았지만 실제 wordnet, freebase를 KG로 사용한 Link Prediction task에서 TransE도 충분히 훌륭한 성능을 보인다.

따라서 KGE를 적극 활용하고자 할때는 하나의 KGE방법만을 정한다기보다는 여러 가지를 사용하고 Ablation study를 해보는 것이 좋아보인다.

References

• https://ieeexplore.ieee.org/document/8047276
• https://arxiv.org/pdf/2210.09338.pdf
• https://arxiv.org/pdf/1905.07854.pdf
• https://github.com/thunlp/OpenKE