신윤종 지음
Contents
- Reasoning over Knowledge Graphs
- Path Queries
- Conjunctive queries
- Query2Box
Reasoning over Knowledge Graphs
Knowledge Graphs
- Knowledge 즉, 지식을 그래프의 형태로 구성한 것
- node = entity (labeled with type)
- edge = relationship
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F7b78713e-4690-4b19-8439-bbf280690a44%2Fimage.png)
KG Representation
- KG에서의 edge는 triples(h, r, t)로 임베딩 할 수 있다
- head(h): 출발노드(앵커 노드)
- relation(r): edge, 관계
- tail(t): 도착 노드
- 우리의 KG를 임의의 차원으로 임베딩 시키고 실제로 연결되어있는 true triple(h, r, t)가 주어졌다고 해보자
- Ex) h(기생충)의 r(감독) t(봉준호)
- Q1) 기생충의 감독은 봉준호. 즉, h에서 r만큼 이동한 위치가 t의 위치와 똑같아야 겠지?
- Q2) 그러면 (h, r)을 어떻게 임베딩 시킬까?
- Q3) 두 노드 간의 거리는 뭘로 정의하지?
Relation Patterns
Relation의 특성 3가지를 살펴보자
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F80dd37c2-3310-4e68-b971-80924dc503d6%2Fimage.png)
TransE
앞서 Graph representation에서 배웠던 TransE를 써먹을 수 있을 것 같다.
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F16feaf4f-bcd6-422c-816b-b7c65d842bf6%2Fimage.png)
- TransE는 h, r, t를 임의의 차원에 매핑하는 임베딩 방법이다.
- h에서 r만큼 이동한 위치가 t의 위치가 같을 수록 좋다!
TransE Training
TransE는 어떻게 학습할까?
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fbed87df2-833d-4159-8093-bb26ed61951c%2Fimage.png)
1. True triple과 Corrputed triple(가짜) 2가지를 뽑고 2가지 값과 임의의 마진값의 합을 maximize한다
- True tiple의 거리가 가까울 수록 좋다
- Corrupted tirple의 거리가 멀 수록 좋다
Link Prediction using TransE
- TransE는 Link prediction에 써먹을 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F5a383bb4-0892-4827-bfef-cd0394d22711%2Fimage.png)
Composition in TransE
- KG의 특성인 Composition을 만족한다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ffa73cdac-4baa-4a9c-ac94-3a70394c9d91%2Fimage.png)
Limitations
- 그러나 TransE는 2가지의 KG 특성을 만족시키지 못한다.
Symmetric relations
- 만약 r이 0이라면 symmetric 특성에 따라 h와 t가 같아야하지만, 실제로 매핑된 TransE값을 보면 h와 t는 서로 다른 벡터이다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F7be2b23c-c015-4abb-a3a0-62818946f4ed%2Fimage.png)
N-ary relations
- 일대다, 다대일, 다대다 관계를 만들 수 없다
- 만약 (h, r)의 결과인 t가 많은 경우
- t1 = h+r
- t2 = h+r -> t1과 t2는 같아야한다
- 그러나 t1 != t2
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fa075429c-8c7e-48b9-8c7d-f82218117e8f%2Fimage.png)
TransR
- TransE와 동일하게 entity vector를 임의의 d차원을 매핑한 후 각 relation을 vector r로써 다른 k차원에 매핑한다.
- 임베딩 매트릭스 Mr의 shpae은 (k, d)
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fb9c3c624-360a-4316-adb3-56d452c769d1%2Fimage.png)
Symmetric relation in TransR
- TransR은 symmetric 특성을 보존할 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F158ee395-46c4-4e1e-b6df-779eb7a87868%2Fimage.png)
N-ary relation in TransR
- 일대다, 다대일, 다대다 관계도 지킬 수 있다
- d차원에서 다른 노드더라도 r을 통해 k차원으로 매핑시킨다면 같은 값으로 임베딩 될 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F93966659-a1d1-43ce-a21e-4c5b3f207b72%2Fimage.png)
Limitation
- 그러나 TransE와 반대로 composition 관계를 보전할 수 없다
- 왜냐하면 TransR에서 모든 r은 각자 다른 space에 매핑하는 역할이기 때문!
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fa5816fa0-3e04-4f7c-9127-e84444292ab8%2Fimage.png)
Translation-Based Embedding
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fd0e685eb-e0c5-4949-9db3-aad2eae2069c%2Fimage.png)
Path Queries
Query type on KG
- 만약 multi-hop reasoing을 진행한다면 어떻게 될까?
- 복잡한 질의를 불완전하고 거대한 KG가 다룰 수 있을까?
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F99df9e43-b1af-437d-90b0-5ed4fa93b129%2Fimage.png)
One-hop queries
- 간단한 one-hop 질의는 link prediction으로 생각할 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F1f754c84-e9e1-42c0-8121-da65a961d79c%2Fimage.png)
Path queries
- one-hop을 일반화하여 여러 단계로 나누어 path를 구성하여 질의를 진행할 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fb3cd0dcb-4a41-4855-8684-321f3f477d73%2Fimage.png)
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Faa6c35ea-9bea-42d2-85bb-695fdacb2a5c%2Fimage.png)
Traversing KG
-
KG에서 multi-hop을 진행해본다고 해보자
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F9f8577f8-4c13-457a-8eef-678fa1a8fcaf%2Fimage.png)
-
IDEA 1) one-hop처럼 link prediction으로 KG를 횡단할 수 있지 않을까?
- NO! KG는 dense graph이기 때문에 매 스텝마다 모든 노드와의 link 확률을 구한다면 시간복잡도는 path의 길이가 n이라면 O(∣V∣n)이 걸린다!
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fcbe3ef5e-0d04-48cb-8530-e65efef2a1ee%2Fimage.png)
-
IDEA 2) query를 임베딩하자
-
TransE를 multi-hop reasoning에 사용할 수 있을 것 같다 -> Compoistion을 만족하니까!
-
score function은 ||q - v||로 바로 구할 수 있으니까 훨씬 빠르다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F02162422-3aa3-41a7-9206-e1fe765b8963%2Fimage.png)
Traversing KG in vector space
- TransE를 활용한 multi-hop 예시를 보자
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F68d3579d-2ffe-4972-9bc1-0f9029b79ee1%2Fimage.png)
Conjunctive queries
- 더 복잡한 질의는 어떻게 다룰까?
- 만약 multiple ancohor node에서 출발하면?
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ff6d5a435-15a7-4c4d-a5b0-393825c11f38%2Fimage.png)
- 과정을 살펴보자
- anchor node 각각 출발하여 두 relation이 겹치는 node를 찾는다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fe13db3c9-63ce-4ca8-8b09-231fc27b7059%2Fimage.png)
- multi-hop을 진행한다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F4a17e0c5-1d58-4dd9-9296-c6ae5ffe4a1e%2Fimage.png)
Traversing KG in vector space
Neural intersection operator
- 여러 query를 받아서 intersection을 찾아야 한다
- 전지전능 neural intersection operator J를 모델링하자
- Input: query embedding set (q1,...,qm)
- Output: intersection embedding q
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ffdeefa9a-b2e5-424e-9f4b-71d8fecc4a32%2Fimage.png)
- 그러면 우린 성공적으로 intersection을 찾을 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fd2128ed4-8b36-46a8-8e59-0226baee68fc%2Fimage.png)
Training
- entity embedding v와 query embedding q가 주어졌을 때
- score function = ∣∣q−v∣∣
- parameters
- entity embedding: d∣V∣
- relation embedding: d∣R∣
- intersection operator φ, β: 그래프 사이즈에 영향받지 않음
- TransE하고 똑같이 학습하면 됨
- query q, answer v, negative sample v'를 샘플링한다
- q를 임베딩한다
- v와 v' score를 구한다
- loss 최적화 한다
- Evaluation
- test query q를 임베딩한다
- 모든 triple v에 대하여 score를 구한다
- ditance rank를 구하여 prediction한다
- Limitations
- 단순히 intersection vector 하나 구하는 것은 직관적이지 않음
- 정답이 될 수 있는 후보군을 추릴 수 없을까?
- 기하학적으로 더 설득력있는 답을 내놓고싶은데...
Query2Box
Box Embeddings
- query를 box로 임베딩하자
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fc97cbd10-a469-443e-bf3b-462493acab1c%2Fimage.png)
- 기존 intersection vector를 구하는 방식에 비해 더 직관적이다!
Embed with Box
- parameters
- entity embedding: 크기가 0인 box로 초기화
- relation embedding: 2d∣R∣ center와 offset때문에 2개씩 만든다
- intersection operator φ, β: 그래프 사이즈에 영향받지 않음
- input으로 box를 받아서 output으로 box를 뱉을 예정
Projection operator
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F26ecf114-c642-4320-809d-8507c7625d75%2Fimage.png)
- path가 진행될 수록 box는 계속 커지며 간단히 생각해서 error에 해당되는 부분이라고 보면 된다
Embed with Box
- 기존 intersection vector를 구하는 방식과 달리 box를 임베딩하였다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F24704a8e-13d3-4ced-8d9c-5ce7a41c5b37%2Fimage.png)
- 모든 box의 교집합 부분을 intersection box로 본다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fb879fe37-a464-4171-a32c-5d9068af7afb%2Fimage.png)
- center는 weighted average로 정한다
- new offset은 줄어든 것을 알 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fef7b1ec8-0a0c-428b-865f-9c63a062871d%2Fimage.png)
- 이를 embedding space 관점에서 살펴보자
- intersection box를 구하고, 다음 매핑에서 새로운 box를 만들었다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fee4ad78b-525d-4822-899f-6a5927537acb%2Fimage.png)
Entity-to-Box distance
- query box q와 entity vecotr v가 주어졌을 때 distance를 구해보자
- q에서 시작해서 v까지의 L1 norm을 distance로 정의할 수 있고 알파를 조절하여 box q의 영향을 조절할 수 있다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F9da500be-278f-42a1-bab0-bef8839c135d%2Fimage.png)
Training
- loss를 minimize하는 방식으로 학습한다
- 좌항에서 true box score를 minimize하고, 우항에서 false box score를 maximize한다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F9b04444a-2bbe-4b24-9d48-4082b920aca6%2Fimage.png)
Relation patterns
- 결론 Leskovec 교수가 갓이다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ff045f760-9f63-494a-9b17-5f602883f239%2Fimage.png)
EPFO queries
- Existential Positive First-order (EPFO) : Conjunctive queries + disjunction
- 기존 embedding 방법으로 처리할 수 있다
- Process
- 모든 union이 걸린 노드마다 최종 목적지인 vparent를 선택한다
- 모든 union edge를 제거한다
- 모든 union node를 순회하면서 v와 vparent로 새로운 compuation graph를 조직한다
- 쉽게 생각해서 모든 경우의 수를 따로 나누어서 graph를 만든다고 보면 된다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fe98d3a20-cf58-4700-9924-5152fedb5fcd%2Fimage.png)
Knowledge Graph
는 지식을 그래프 형태로 구성한 것으로,node
가 entity 가 되며,edge
가 relationship 이 됩니다.𝒉(head entity), 𝒍(relation), 𝒕(tail entity) =
(𝒉, 𝒍, 𝒕)
node 와 relationship 을 triplet 형태로 표현합니다.
Knowledge Graph 에서는 Link Prediction 이 활발하다고 합니다.
TransE
(𝒉, 𝒍, 𝒕) 를 임의의 차원으로 mapping 하는 embedding 방법론으로,
Valid triplet 이 클수록, Corrupted triplet 이 작을수록 좋아지도록 margin loss 를 설정합니다.
transE 는 Composition Relations, 즉 relationship 간의 관계를 형성함으로써 또 다른 relationship 을 표현할 수 있다는 장점이 있지만,
Symmetric Relations 과 N-array Relations 를 표현할 수 없습니다.
TransR
TransR 은 entity 와 relation 을 동일한 semantic space 에 두지 않고, 구분된 공간에 embedding 하는 방법입니다.
Symmetric Relations 및 N-array Relations 을 표현할 수 있다는 장점이 있지만, Composition Relations 를 표현할 수 없습니다.
Path Queries
multi-hop reasoning 을 진행하기 위한 방법론이며, one-hop 을 일반화하여 여러 단계로 나누어 path 를 구성하여 질의를 진행합니다.
one-hop 을 여러 번 타고 타고 계산하는 방식은 시간복잡도 측면에서 비효율적이기 때문에,
query embedding
하여 계산하는 방식으로 진행합니다.Conjunctive Queries
더욱 복잡한 질의의 경우 (교집합), 1. intersection 을 찾고 2. multi-hop 을 진행합니다.
이 때, 실제 embedding space 에서 하나의 점으로 표현되지 않기 때문에,
Neural Intersection Operator
를 이용해 이를 해결합니다.각각의 query 마다 embedding 을 진행하여 neural network 를 통과시키고, 이를 통합하여 intersection query 를 만들어 냅니다.
Query2Box
intersection vector 하나만 구하는 것은 직관적이지 않기 때문에,
query
를box
로embedding
하여,intersection box
를 사용합니다.query box q 와 entity vector v 에 대하여, v 를 q 로 나타내고자 할 때, Entity-to-Box distance를 고려합니다. parameter α 를 통해 q 의 offset (=영향력, 중요도) 를 조절할 수 있습니다.
Query2Box 또한, Positive Box 를 maximize 하고, Negative Box 를 minimize 하는 Loss 를 설정해 training 을 진행합니다.
그천 (그래프 천재) 윤종님 띵강 감사감사 합니다 ~