Chapter17. Reasoning over Knowledge Graphs

What is knowledge Graph?

Graph에서 Knowledge들은 entities / types / relationships로 나뉘어져 있음. 각 node들은 고유의 entitles(이름 같은 것들)이 있으며 그에 대한 type이 정해져있음. 또 node들은 Edge로 relationship을 표현할 수 있다.

ex) '박진혁'이라는 node는 '사람'이라는 type으로 labelling 되어 있으며, '투빅스'라는 node(type은 club)에 member라는 relationship을 가지고 있다. 와 같이 표현이 되는 것이다.

예시

구글에서의 knowledge Graph 예시

그래서 이걸 QA모델에도 적용할 수 있다. (QA모델도 모르는데 이걸 내가 한다는 건 무엇인가 잘못됐다는 걸 이시점에서 느꼈따)

즉 위 그림과같이, 추수감사절, travel, NY과 같은 키워드가 있으면, NY 에 속해있는 JFK 공항, Thanks giving에 해당하는 연관 노드들에 접근해 answer를 유도할 수 있게 되는 것이다

그러나 knowledge graph라고 볼 수 있는 대부분의 것들은 (위키피디아를 생각해보자)

1. Massive하고

2. Incomplete 하다

-> 그렇다면 missing edge들을 꽤 잘 연결할 수 있는 방법이 있을까?

Embedding

Freebase라는 곳에 있는 데이터르 모델로 둬보자. KG에있는 edge는 크게 세 가지 상태로 표현이 된다.

시작점(head), 도착점(tail), 그리고 그 노드의 관계(relationship).

그래서 핵심 아이디어는 entitles와 realtion을 아주 잘 modeling해보자는 것이다. true (h,r,t)가 있을때 이를 이용해 (h,r)을 임베딩 해보자는 것이 목표이다.

다만 그 전에 relation의 경우는 몇 가지 특수한 경우들이있다.

1. Symmetric Relation : A 와 B는 symmetric해야하는 경우가 많다. 어떤 가족의 구성원들은 서로간의 관계가 가족이며, 어떠 집단의 무리가 있으면 그 집단 내에서 각 사람들의 관계는 friends일것이다.

2. Compostion Relation : 나와 아빠의 관계는 나와 엄마의 관계 + 엄마와 남편의 관계이다. 즉, 나라는 벡터에 엄마라는 벡터와 남편이라는 벡터를 합치면 아빠라는 벡터가 나와야한다.

3. 1 - to -N, N-to-1 투빅스라는 entity와 투빅스 멤버들의 entity의 관계는 모든 투빅스 멤버에 대해 member of가 된다. 즉, 하나의 entity에 특정한 벡터들를 연산하면 여러 relationship이생길 수 있다.

사실, Node와 Edge를 embedding하는 방법은 앞에서 하나 배웠다.

Trans_E head + realationship = Tail이 나오게끔 embedding하는 것이다. 다만 이렇게 되면 큰 문제가 발생한다.

1. Symmetric : h + r= t, t+r = h를 모두 만족해야한다. 즉 t - r = t + r, r= 0이 된다. 즉 대칭적인 벡터는 존재할 수 없게 된다.

2. composition : 이것은 엄마 벡터 + 남편 벡터 = 아빠 벡터 가 나오게 할 수 있으므로 성립한다.

3. 1 to N : 투빅스라는 벡터에 멤버 벡터를 더하면 투빅스 멤버들이 나와야하지만, 이렇게 하게 되면 멤버 벡터가 하나밖에 나오지 않는다.

=> 위 문제들을 종합해보면 Trans_E는 임베딩하기에 좋지 못한 수단이다.

Trans_R

TransR은 다음과 같이 모델링 하는것이다. relation을 Matrix를 이용해 만들고, head vector에 Matrix를 곱하면 head projection (Vector space의 크기는 같다)과 tail projection이 나온다. 그리고 relation은

|hㅗ + r - tㅗ |로 정의하는 것이다.

이제 따져보자

1. Symmetric : 표현가

2. 1 to N, N to 1 : 표현가

3. Composition Relation => 불가

여기서 주의해야할 점은 Mr은 모든 relation에 대해 존재한다는 것이다.

Path Query

이 때 Query는 총 4가지 종류가 존재하는데 각각 어떤 역할을 하는 지 알아보자

One-hop Queries는 단순하다 A와 B의 관계가 r이라면 A라는 시작점과 r이라는 관계가 주어졌을 때 B로도달할 수 있는 것이다.

여기서 새로나오는 개념은 Path 이다. 어떤 이어지는 것들이 있을 때, 이것들은 어떻게 계산할까? 일단 정의는 다음과 같은 방식으로 표현한다. 시작점 Va와 relation을 나타내는 r벡터들을 통해 나타낸다.

그리고 다음과 같이 계산된다

먼저 r벡터를 통해 그에 해당하는 Entity로 이동하고 또 거기서 r2벡터를 통해 또 그에 해당하는 벡터로 이동한다. 즉 도식화하게되면

와 같이 표현이 되는 것이다. 그런데 실제 KG는 매우매우 많은 node들과 연결이 되어있다. 즉 Path가 길어지면 길어질수록 Geometric하게 경로가 길어지게 되는 것이다.

그렇기 때문에 우리는 transE를 이용해 Path를 한번에 임베딩할 것이다.

즉 이런 식으로 여러 벡터를 한 번에 이동함으로써 연산을 줄일 수 있다.즉 누나의 친구들이라고 하면 누나 라는 관계를 모두 찾아서 이동한 뒤, 거기서 친구벡터들을 다시 다 찾아가는 것보다는 누나 + 친구 벡터를 해서 한 번에 도달하게하는 것이 효율적이라는 것이다. (그런데, 이러면 친구아빠랑 아빠친구랑 구분이 안되지않나..?)

또 관련 논문을 찾아보면

이러한 내용도 찾아볼 수 있는데, 만약 아빠 라는 벡터가 수평이라고 하면 나의 아빠로 이동하는데 노이즈가 약간 낀다. 그런데 아빠의 아빠 벡터인 할아버지 벡터가 가게되면 이 에러가 갈수록 커지게 되는 것이다. 이러한 관점에서도, 시작점 + relation 벡터들을 더해서 나온 q벡터와 실제 도착해야하는 점인 v벡터를 통해 계산하는 것은 분명 이점이 존재한다.

Conjunctive Queries(논리곱~)

Conjunctive라는 말은 쉽게 말해서 And라고 생각하면 된다. 즉 Canadian이면서 Turning award 수상자는..? 을 찾을 때 어떻게 찾아야할까?

이런식으로 Canadian + Citizen을 먼저 구하고 Turing Award + win을 구해서 두 intersection(교차부분..?)을 구하는 것이다. 사실 직관적인 Projection은 이러한데 저렇게 벡터가 딲딲 맞게 떨어질까?

현실은 이렇다.. 두 부분의 q1과 q2의 교점을 찾아야하는데 현실적으로 교점이 생길리가 없다. 그렇기때문에 그 두부분이 교차하는 점 구해야할 것이다. 위 그림만 보면 우리는 힌톤과 벤지오가 사이어딘가를 교점이라는 것을 알 수 있다. 그런데 이런 직관적인 경우가 아니라면 InterSection을 구하는 것은 큰 문제가 되는 것이다.

요즘 우리는, 딥러닝의 시대에 살고있다. 모르겠으면 Neural Network를 도입하자. 현재 query들을 input으로 놓고 output을 intersection point 나오게 NN을 만들어보자.

다음과 같이, 각 벡터들을 넣는데 permutation invariant하다.. 캐나다인인 우승자나, 우승자인 캐나다인이나 같으니 직관적으로도 당연하다.

다음과 같이, 모든 벡터를 넣고 Neural Network를 통과하고 전체를 Mean한다. 앞에 GCN할 떄도 연결된 모든 노드들의 평균을 내는 것처럼 그래프에서는 평균을 내는게 아주 자유롭다. 그 이후 다시 네트워크를 통과시켜 intersction을 얻을 수 있게 된다.

다음과 같이 구해지는 것이다. q1과 q2의 intersection을 구하고 그 벡터에 graduate 벡터를 구해 그 이웃들을 answer로 구하는 것이다.

여기서 파이나 베타는 graph size에 영향을 받지 않는 파라미터로 트레이닝 할 수 있다.

Box Query

위에서 intersection의 영역을 구할 때 (특정 벡터에서 가까운 것들을 구할 때) 사람이 조정하기 때문에 직관적이지 않다는 점이 있다. 그래서 우리는 새로운 Box query라는 것을 도입한다.

Box Embeddings : queries를 hyper rectangle로 emnedding하는 것

다음과같이 Center와 offset으로 정의할 수 있다.여기서 offset은 q와 같은 dimension인데 각 dimension별로 어느정도의 offset을 가질지 결정하는 것이다.

이 때 parameter들은 다음과 같은데 의미를 잘 살펴보.

entity embedding은 d의 dimension이고 공간상에서 한 점을 나타내는 것이다. 공간상의 한 점은 결국 offset이 0이고 Center가 entity embedding을 나타낸다고 할 수 있다. relation embedding은 앞에 2가 붙는데 저 위에서 정의했듯, Center와 Offset이 모두 있기 때문이다.

또한 Geometric한 연산으로 Box X Relation = Box라는 결과가 나오는데, 사실 왜 X라는 연산을 썼는 지는 잘 모르겠지만, 어떤 두 점을 더할 때는, Center끼리 더해서 새로운 Center를 만들고 offset끼리 더해서 새로운 offset을 만들게 된다. (만약, entity라면 같은 offset을 가지고 중심만 이동할 것이다) 이렇게 되면 결국 전체 박스의 크기는 갈수록 커지게 될 것이다.

그렇다면 Box X Box의 Operation은 어떻게될까?

다음과 같은 식으로 찾게 된다. 그런데 그림에서는 그냥 다 겹치는 부분만을 찾았지만, 새로운 벡터는 다른 방식으로 정의된다.

일단 새로운 Center는 기존 box들에 weighted sum이라고 할 수 있다. 이러한 weight는 학습되는 것이라고 생각하면 된다. 그리고 offset의경우 일단 mean 값을 취하기 때문에, intersection이 생기면 offset이 줄어든다. 그런데 저 deepsets은 조교님 말을 알아듣기가 힘들어..(사실 count라고는 하는데 count가 진짜 내가 이해한 것이 맞는지도 모르겠어서 해당 논문을 읽어보았다.)

해당 논문에서는 각 벡터를 Mlp에 넣고 평균낸 것을 다시 MLP에 넣는다. 아마 input은 d (벡터 스페이스의 차원)을 모든 Set에 대해 mlp에 넣고 그 mlp의 output은 d dimension이 될 것이다. 그것 다시 넣어서 (dXN) 차원을 return하는 것 같다.

결국 다음과 같이 직관화된다.

그리고 이 원래 True node와 box의 거리는 다음과 같이 정의된다.

로스는 TransE와 비슷하게 정의된다.

박스안에 있어야할 것들은 거리를 최대한 줄이고, 박스밖에 있어야할 것은 거리르 최대화 하는 방향으로 트레이닝해야한다.

이렇게 query를 박스로 임베딩하면 위에서 만족해야했던, symmetric composition 1toN이 모두 만족된다.

강의에서는 설명하지는 않았지만 symmetric이 약간 비직관적이여 살짝 짚고 넘어가자

symmetric의 경우 Cen(r)을 0으로 하면 된다. 즉, head와 tail의 경우 나라는 entity가 있고, 거기에 Offset만 더하면 그 offset 범위내에 엄마가 있으면 되고, 엄마 entity에서 offset을 구하면 또 그 범위에 내가 있을 것이다. 따라서 symmetric의 경우 Cen(r)이 0가돼야한다.

Composition과 1toN의 경우는 자명하다.

*EPFO query? : Conjunctive + disjunction query => and + or query! 캐나다인이면서 turing이나 노벨상받은 졸업생? 과 같이 and와 or이 모두 들어간 쿼리의 경우에도 box를 이용해서 잘 임베딩할 수 있고 한다.

Experiment

실험부분은 결과가 많아서 피피티로~