Learning Entity and Relation Embedding for Knowledge Graph Completion

  이번 포스팅에서는 knowledge graph에 대한 대표 연구 중 하나인 "TransR" 모델에 대해 살펴보겠습니다.
해당 연구는 graph embedding에 대한 대표적인 선행연구로써, 사전 지식 확보를 위해 graph embedding의 개념과 TransR 이전 연구들인 TransE, TransH 및 평가(evaluation) 방법론에 대해서도 살펴보도록 하겠습니다.

 

 

  knowledge graph가 무엇인지에 대해 위키피디아는 아래와 같이 정의를 내리고 있네요.
"지식 그래프는 다양한 소스로부터 축적한 시맨틱 검색 정보를 사용하여 

                                              검색결과를 향상시키는 것으로 구글이 사용하는 지식 베이스이다."
여기서 "다양한 소스"라는 것은 대상의 개념을 나타내는 entity라고 생각하면 될 것 같습니다. 또한, 세상 속의 모든 대상은 서로 다른 대상들간 관계(relation)를 맺고 있습니다. 이 둘을 결합하여 그래프 구조로 표현한 것이 knowledge graph라고 보면 됩니다. 즉, node(=vertex, entity), edge(=relation)으로 구성된 데이터 구조인 graph와 동일한 것이죠.

  knowledge graph를 표현하기 위한 다양한 방법이 있습니다. 그 중 대표적인 방법 중 하나는 온톨로지(Ontology)이죠.
온톨로지는 세상의 여러 개념들과 그 사이의 관계를 RDF, OWL 등의 언어로 표현함으로써 추론이 가능한 많은 장점이 있지만, 도메인 전문가들의 지식으로 온톨로지 설계가 필요 표현함으로써 추론이 가능한 많은 장점이 있지만, 도메인 전문가들의 지식으로 온톨로지 설계가 필요하다는 한계가 있었습니다. 그렇기에 어떻게 머신러닝 모델으로 그래프 데이터 내부의 의미를 추출할 수 있을지에 대한 연구가 지속되고 있습니다. 한 가지 전략은 graph embedding입니다. 이로써 각 node를 vector화 시킬 수 있고, vector간 유사도 계산이 가능합니다. 

일반적인 그래프 데이터는 아래와 같이 구성되어 있습니다.
node와 node를 연결시키는 relation으로 표현된 triplet 형식이죠.
(n1, n2), r1
(n1, n3), r1
(n3, n4), r2

그래프의 특성에 따라 방향의 존재 여부가 달라집니다. 예시는 방향이 있는 그래프입니다.
이때, 모든 triplet은 아래와 같이 정의 가능합니다.
(head, tail, relation)
그렇다면, node와 relation을 어떻게 vector로 표현할 수 있을지에 대한 고민이 필요합니다.

여러분들이 만약 처음 이런 이슈에 맞닥뜨렸다면 어떤 해결책을 고안했을까요?

 

 

TransE

Bordes, Antoine, et al. "Translating embeddings for modeling multi-relational data." 

Advances in neural information processing systems. 2013.

 

가장 기본적인 방법인 TransE 모델은 아래와 같은 objective function을 가집니다.

head + relation = tail

즉, head와 relation vector의 합은 tail과 (최대한) 같아져야 한다는 것입니다. 이는 논리적으로도 타당합니다.
하지만 현실적으로 해당 수식이 equal이 되기는 불가능합니다. 그래서 score function은 head+relation의 지점에서 가장 가까운 node가 tail이어야 한다는 목적을 갖습니다. 그래프에 있는 모든 triplet을 상기 조건을 충족시키는 방향으로 학습 한다면 node와 relation에 대해 embedding이 가능합니다.

 

TransE 모델의 objective function은 아래와 같다.

 

모델 train을 위해서는 training set에 있는 postive triplet뿐만 아니라, negative sampling이 필요합니다. 해당 연구에서는 tail node를 바꾸는 것으로 negative sampling을 수행하였고, margin은 (일반적으로) 1로 설정하였습니다. 학습은 모델의 loss를 최소화하는 방향으로 수행됩니다. 즉, max(0, d_pos-d_neg+margin)의 값이 항상 0이 나오는 경우가 이상적인 경우이죠. 이를 위해서는 d_pos-d_neg+margin(=1) < 0이 되어야 하며, d_pos+margin(=1) < d_neg가 되어야 합니다. 다시 말해, postive sample의 distance가 negative sample의 distance보다 최소한 margin만큼은 가까워야 합니다.

 

해당 전략은 1:1 relation일 때는 상당히 우수한 성능을 나타냅니다. 하지만, 1:N, N:1, N:N과 같은 경우에는 이슈가 발생합니다.  아래와 같은 상황을 가정해볼까요?
(John, Book) like
(Mike, Book) like
(Harry) like
John, Mike, Harry 세명 모두 book을 좋아하는 구조입니다.
이는 subject(head) verb(relation) object(tail)로 생각할 수 있습니다.
TransE 모델에 따르면 h+r=t이란 objective function으로 모델링한 결과는 John=Mike=Harry가 될 정도로 3개의 head는 매우 가까운 similarity를 가질 것입니다. 즉, 사람 고유의 특성(e.g. 성격, 나이, 성별, 취미)은 잡아내지 못하고 3개의 head(entity)는 동일하게 학습될 것입니다.

 

TransE는 여러 relation에 속한 entity라도 모두 동일한 representation을 갖게되는 한계가 있습니다.

아래와 같이 Many to One mapping을 가진다고 예를 들어보겠습니다.

(Mike, Book) like 
(John, Book) like 

 

그리고 추가적인 relation인 dislike을 하나 더 정의하도록 하겠습니다

(Mike, Cherry) dislike

 

아래 상황과 같이 graph embedding이 된다면 loss가 0인 이상적인 학습이 이뤄진 것입니다.

즉, 아래 3가지 조건을 모두 만족하는 상황입니다.

   - 1. Mike+like=Book

   - 2. John+like=Book

   - 3. Mike+dislike=Cherry

앞서 이야기한 바와 같이 "여러 relation에 속한 entity가 모두 동일한 representation이 되는 한계"가 나타납니다.

Mike와 John은 모두 Book을 like하기 때문에 비슷한 위치에 embedding 되는 것이 타당합니다. 하지만, Mike는 John과 다르게 cherry를 dislike하는 특징이 있습니다. (즉, 2개의 relation에 속하는 entity입니다)

 

이처럼 entity마다 여러 relation에 영향을 받을 수 있기 때문에 이를 모델링 과정에서 고려할 필요가 있습니다. (그래서 Mike와 John의 embedding space는 지금보다는 distance가 커지도록 모델링할 필요가 있습니다)

 

 

 

 

 

TransH

Wang, Zhen, et al. "Knowledge graph embedding by translating on hyperplanes." 

Twenty-Eighth AAAI conference on artificial intelligence. 2014.

 

TransH 모델은 relation을 (relation-specific) hyperplane에 투영(projection)시킴으로써 앞선 이슈를 해소하였습니다. 각 node도 해당 hyperplane으로 투영시킴으로써 모든 node는 각 relation마다 구분될 수 있습니다. 연구에서는 이를 "distributed representations of entity"라고 부릅니다. 

 

 

 

 

TransH의 objective function과 head, tail node를 투영시키는 연산은 아래와 같습니다. 각 relation마다 2개의 vector를 가지며, w_r은 entity(head, tail)를 hyperplane으로 투영시키는 (relation-specific) norm vector이며 d_r은 (relation-specific) translation vector입니다. 이처럼 TransH는 hyperplane으로 entity, relation을 projection시킴으로써 아래와 같은 score function을 정의합니다. (이로써 TransE에서 이슈가 되었던 "동일 entity가 여러 relation에서 구분이 안된다"는 문제를 해결할 수 있었습니다.)

 

Score function of TransH

 

모델 train을 위한 objective function은 아래와 같습니다. TransE와 동일하게 margin(γ)이 존재하며, positive, negative sample을 사용하여 학습을 수행합니다.

 

 

 

 

 

 

TransR

Lin, Yankai, et al. "Learning entity and relation embeddings for knowledge graph completion." 

Twenty-ninth AAAI conference on artificial intelligence. 2015.

 

TransR은 앞서 소개드린 TransE, TransH의 어떤 부분을 개선할 것일까요? 앞선 두 model은 entities와 relations이 모두 같은 embedding space에 있다는 전제가 있습니다. 독자분들은 이렇게 생각할 수 있을 것 같습니다. "TransH는 relation마다 구분되는 (relation-specific) entity를 가지기 때문에 문제가 없지 않냐"구요? 이처럼 의문을 가졌다면 여러분은 TransH을 어느 정도 잘 이해한 것이라 생각합니다. 그렇지만 다시 생각해보죠. TransH는 단순히 다음과 같은 역할을 수행할 뿐입니다.

  "TransH is proposed to enable an entity having different representations when involved in various relations."

즉, entity를 hyperplane에 투영시킴으로써 다양한 relation 사이의 관계를 학습한 representation이 생기는 것이죠.

그 결과 지금까지 소개드린 모델들은 entity(head, tail) relation이 모두 같은 embedding space에 존재하게 됩니다. 

이는 무엇을 의미할까요? 사실 entity와 relation은 명확하게 다른 object입니다. 그렇기에 이 모두를 같은 semantic space에 embedding 하는 것은 적합하지 않습니다. TransH는 (relation-specific) hyperplane을 고안하였지만, 이 역시 동일한 한계를 가지고 있습니다.

 

도대체 entity와 relation이 동일한 semantic space에 있으면 무엇이 문제인 것일까요? entity는 여러 특성(aspect)을 갖습니다. 그리고 다양한 relation들은 entity의 다른 요소(aspect)들에 집중합니다. 예를 들어, r1 측면에서는 e1, e2가 유사한 점이 존재했지만, r2 측면에서는 e1, e2가 유사한 특성을 갖고 있지 않다고 볼 수 있습니다.

 

이런 한계를 극복하기 위해 TransR은 entity와 relation을 구분된 공간(entity space, multiple relation spaces)에 embedding하자는 아이디어를 제안했습니다. 또한, entity의 translation을 위해 TransR은 relation-specific projection을 수행하는 "projection matrix"를 사용함으로써 entity를 entity space에서 각 relation space로 embedding 시킵니다. 

 

위 이미지 좌측을 보면, entity space에 h(head), t(tail) 뿐만 아니라, 여러 삼각형이 있습니다. 여기서 r(relation)이 존재하는 entity는 단지 h, t뿐입니다. 해당 entity들을 relation r이라는 relation space으로 projection시키기 위해 M_r이라는 projection matrix를 활용합니다. 그 결과는 우측에 보시는 relation space of r입니다. 좌측에 비해 h와 t은 r이라는 relation 관계가 있기 때문에 서로 가까운 공간에 위치하며, 이외의 r 관계가 없는 entity(삼각형)들은 서로 멀어졌습니다. 이로써, TransR은 relation별로 다른 entity embedding을 가지는 장점을 가집니다.

 

TransR을 수식으로 설명하자면 아래와 같습니다. 먼저 M_r이라는 projection matrix로 entity를 relation space로 projection시킵니다. 그 이후, h+r=t 이라는 기존의 objective를 만족시키는 방향으로 모델 train을 수행합니다.

Definition of the projected vectors of entities

Objective function of TransR

 

TransR 역시 TransE, TransH와 동일하게 negative sampling과 margin(r)의 개념을 동일하게 사용합니다.

 

 

 

지금까지 knowledge graph embedding의 대표 방법인 TransE, TransH, 그리고 TransR에 대해 살펴봤습니다. 각 모델의 한계들과 그 한계를 어떤 방법으로 극복하고자 했는지를 파악한다면 여러분이 만나는 각종 문제들을 극복하는데 도움이 되지 않을까 생각합니다.

 

다음 포스팅에서는 graph embedding이 잘 되었는지 평가하는 방법론에 대해서 살펴보도록 하겠습니다. :)