[Study]Chapter 11. Reasoning over Knowledge Graphs

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

이번 챕터에서는 KG에서의 질문 쿼리를 이야기 합니다.

I. Reasoning in KG using Embeddings

KG에서 multi-hop 추론을 어떻게 수행할까?

reasoning in

추론하다는 뜻으로 KG completion task에서 일반화/확장하여 멀티 홉 쿼리에 대한 답을 예측하는것입니다.

Figure 1 : Queries의 추론 종류

• 1. one-hop queries

  one-hop query: query (h,(r))의 답이 t인가?

• 2. multi-hop path query

  path에 관계를 더 추가함으로써 원-홉 쿼리를 path queries로 일반화한다.

  \[q = (v_a, (r_1, ..., r_n))\]

  Figure 2 : $v_a$는 anchor 엔티티로 answer는 \([[P]]_G\)로 표시되고, query q의 path 쿼리들의 chain이다.

• 3. path queries

  Figure 3 : Fulvestrant로 인한 부정적인 이벤트와 어떤 프로틴이 연관되는가?; e:Fuulvestrant, (r;Causes, r;Assoc)

  Figure 2처럼 표기하면,

  • v_a : e:Fulevestrant
  • (r_1, r_2) : (r:Causes, r:Assoc)
  • Query : (e:Fulevestrant, (r:Causes, r:Assoc))

• 4. conjuctive queries

  Figure 8 : ESR2와 Breath가 어떤 약물에 원인이 되는가; ((e:ESR2, (r:Assoc,r:TreatedBy)),(e:Short of Breat,(r:CasusedBy)))

5. Reasoning

Figure 4 : anchor node(Fulvestrant)에서 시작하여 관계 “Causes”를 가로질러 도착한 노드에서 다시 출발하여 “Assoc” 관계를 가로지른다. 이렇게 도달한 엔티티들이 answer node가 된다.

쿼리에 대해 답을하는 것은 그냥 그래프를 traverse하면 되어 쉬운작업이다 하지만 KGs는 엔티티들 사이의 많은 관계가 소실되어 불완전하다. 따라서, 이러한 KGs의 불완전성 때문에 모든 답 엔티티를 식별하는 것은 어려운 일입니다. 그렇다면 KG completion을 먼저하고 완료된 확률적 KG를 가로지르는 방법은 안될까?

“완전한” KG는 dense 그래프로 (h,r,t)의 세쌍(KG의 edge)은 non-zero 확률을 가지게 되어 path 길이 L에 대하여 시간복잡도(\(O(d_{max}^L))\))가 지수적이게 된어 어렵다.

따라서, 이러한 불완전한 지식 그래프에서 path-based queries에 대한 해답을 찾는 방법이 필요합니다. 이를 위한 접근법은 암묵적으로 값을 채우고 불완전한 그래프를 고려해야합니다.

II. Answering Predictive Queries on KG

핵심은 쿼리 자체를 임베딩 하는것으로 목표는 쿼리 임베딩(q)을 answer 임베딩(t)로 가까이 하는것입니다.

Figure 5 : TransE에서 멀티 홉 추론으로 일반화하는 것으로 h에서 t로 r을 이용해서 횡단합니다.

Predictive queries

소실된 정보를 위해 암묵적인 값을 넣는 동시에 임의적인 쿼리에 답을 하는 작업으로 링크 예측 작업을 일반화한 것으로, 지식 그래프에서 손실된 정보와 노이즈에 대해 robust한 특성을 가집니다.

Figure 6 : \(q = (v_A, (r_1, ..., r_n))\)이 주어졌을때, \(q = v_a + r_1 + ... + r_n\) 임베딩은 vector를 더하는 addition 함수만 포함하여 진행되고 KG에서 엔티티의 수와 독립적이게 됩니다.

이렇게 벡터 공간에서 임베드된 path queries는 아래와 같은 절차를 따르게 됩니다.

Figure 7 : TransE는 composition relation을 다루기 떄문에 이를 다루지 못하는 TransR, DisMul,ComplEx들과 다르게 멀티홉의 잠재 공간에서 횡단함으로써 path queries를 조작할 수 있어 KG를 완전 obejective로 최적화하게 학습할 수 있습니다.

1. Traversing KG

위의 Figure 8처럼 Figure 9에서 쿼리 ((e:ESR2, (r:Assoc,r:TreatedBy)),(e:Short of Breat,(r:CasusedBy)))에 대한 답은 어떻게 찾을 수 있을까?

Figure 9 : Traversing KG in conjunctive queries

Figure9에서 보이듯이 두가지 엔티티(Pacliitaxel, Fulvestrant)를 얻게 되지만 연결이 완전하지 않을때는 답을 찾지 못하게 됩니다. 즉, 지식 그래프가 불완전 그래프면 제대로 찾지 못한다.

그러면 어떻게 암묵적으로 잃어버린 곳에 값을 넣어 임베딩할 수 있을까요?

Figure 10 : entire graph in Figure 9 graph

Figure 10에서 보이듯이 ESR2는 BRCA1과 ESR1과 상호작용하고 두 프로틴은 breat cancer와 연관되어 있습니다.

Figure 8의 문제로 돌아가서 각 중간 노드(회색 원으로 된부분.)는 엔티티의 집합을 표현하는데 이를 어떻게 표현하고, 잠재공간에서의 상호작용 연산을 어떻게 정의할 수 있을까요?

III. Query2box: Reasoning over KGs using Box Embeddings

Query2box¹는 아래와 같이 박스 임베딩이라는 컨셉으로 위의 문제를 해결합니다.

1. Box Embeddings

Figure 11처럼 임베딩 차원에서의 임베드 쿼리(hyper-rectangles)를 가지는 사각형으로 모든 정답 엔티티를 둘러쌉니다.

Figure 11 : embedding space안의 hyper-rectangle query 표현

정답을 찾기 위해 지식그래프를 횡단할때 각 단계에서 접근 가능한 엔티티들의 집합을 계산하는데, 이 집합을 잘 모델링하는 것이 관건입니다. 이를 위한 박스는 강력한 추상화 도구로 중심과 offset을 이용해 엔티티들의 집합을 박스 안으로 둘러싸는 것으로 투영할 수 있습니다.

Figure 12 : (좌)Query Plan으로 질의에 대한 정의를 일반화한 것입니다. (우) 임베딩 영역에서 Box를 통해 Query Plan을 시각화 한 그림입니다.

이러한 Box를 모델링하기 위해서는 아래와 같은 요소를 정의해야합니다.

• 엔티티 임베딩 : # params:d\(\vert V\vert\), 엔티티는 zero-volume box로 나타낸다.
• 임베딩의 관계 : # prams:2d\(\vert R\vert\), 각 관계는 박스를 가지고 새로운 박스가 됩니다.
• intersection operator \(f\) : 박스들의 교차점을 모델링한다.

• Project Operator \(P\) : \(Box \times Relation \rightarrow Box\)

  현재 박스를 입력으로 박스의 투영과 확장에 관계 임베딩을 사용한다.

  \[\begin{array}{ll} Cen(q') = Cen(q) + Cen(r)\\ Off(q') = Off(q) + Off(r) \end{array}\]

2. intersection set of boxes

Geometric 교집합 연산자 J가 필요한데, 이는 여러개의 박스를 입력으로 박스의 교집합을 계산하는 역할을 합니다.

여기서 새로운 박스의 중심은 입력 박스들의 중심과 가까워야 해 offset(box size)는 줄어들게\(_{shrink}\) 됩니다.즉, 박스들의 교집합은 전체 input 박스 크기들보다 작아야한다는 의미입니다.

Figure 13 : \(J : Box \times ... \times Box \rightarrow Box\), \(\circledcirc\):hadamard product로 element-wise product이다.

교집합의 중심(\(Cen(q_{inter})\))은 입력 박스 중심들의 가중합이며 가중치 w는 각 박스들의 중심\(cent(q_i)\)들의 self-attention 점수인 신경망(\(f_{cen}\))을 통해 계산됩니다.

Figure 14 : 신경망(\(f_{off}\))는 입력 박스들의 표현으로 추출되어 표현력을 증가시킵니다. 축소가 보장된 offset은 전체 입력 box의 offset보다 작아야합니다.

입력 박스들의 offset의 최소치를 얻은 다음에 \(f_{off}\)를 통해 추출된 입력 박스들의 표현을 시그모이드 함수로 축소를 보장하여 더 표현력있게 만듭니다.

Figure 12에서 만들어진 교집합이 이렇게 얻어진 박스의 임베딩이다.

3. Entitiy-to-Box distance

어떻게 노드 v에서 쿼리 q로의 반대 거리인 negative distance(\(f_q(v)\)) 를 정의할 수 있을까요?

Figure 15 : \(d_{out}(q,v)=d_{out}(q,v) + \alpha \cdot d_{in}(q,v), where 0 < \alpha <1\), 박스에서 임베딩 포인트가 가깝다면 거리는 작아지게 됩니다.

위와 같은 복잡한 쿼리 임베딩을 Union 연산자를 사용하여 확장합니다. 이를 Existential Positive First-order(EPFO)이라는 conjunctive queries + disjunction한 방법으로 AND, OR 연산자를 사용하여 조합하는 것입니다.

이러한 방법의 쿼리에서 Union 연산자는 고차원의 임베딩이 필요해 저차원 벡터 공간으로 임베딩할 수가 없습니다.

예를 들면 2차원 평면에 박스로 임베딩할때 멀리떨어진 두 점 사이의 다른 점이 있으면 쿼리 박스로의 표현이 불가능합니다. 따라서 AND-OR 쿼리를 저차원의 벡터 공간으로의 임베딩이 불가능합니다.

이를 해결하기 위한 방법으로 아래의 Figure 16처럼 모든 조합을 제거하고 마지막 단계에서만 조합하는것입니다.

Figure 16 : Conjunctive Query AND-OR Plan

4. DNF : Disjunctive Normal Form

AND-OR 쿼리는 DNF형태의 논리식(\((A \wedge B) \vee C\))으로 변환될 수 있는데, \(q=q_1 \vee q_2 \vee \cdots \vee q_m\)가 주어졌을때, \(q_i\)는 연결 쿼리로 모든 \(q_i\)를 처음으로 임베드하고나서 마지막에 조합하는 것입니다.

엔티티 임베딩과 DNF 사이의 거리는 아래와 같이 정의됩니다.

\[d_{box}(q,v)=min(d_{box}(q_1,v), ..., d_{box}(q_m,v))\]

즉, Figure 16의 우측 그림처럼 DNF에서 여러 조건을 OR로 결합하고, 각 조건은 AND로 결합하여 v가 하나의 조건을 만족시키면 DNF 식에 대한 답으로 간주되며 이 벡터들은 가까이 위치하게 될 것입니다.

5. AND-OR 쿼리 q의 임베딩 절차

1. q를 equivalent DNF로 변환 \(q_1 \vee \cdots q_m\)
2. $q_1$을 $q_m$으로 임베드
3. \(d_{box}(q_i, v)\)로 박스 거리 계산
4. 모든 거리의 최소값 선택
5. 최종적으로 score \(f_q(v) = -d_{box}(q,v)\)를 얻음

쿼리 임베딩이 주어졌을때 정답 score \(f_q(v), v \in [[q]]\)을 최대화하고 오답 score \(f_q(v'), v' \notin [[q]]\)를 최소화합니다.

6. Training

쿼리의 정답과 오답을 지식 그래프에서 학습 파라미터로 어떻게 만드는가?

1. 학습 그래프 \(G_{train}\)에서 쿼리 q를 무작위 샘플링
   • 정답 v는 학습 데이터에 존재하고 오답은 존재하지 않습니다.
2. 쿼리 q를 임베드.
3. 정답과 부정 샘플의 스코어를 계산

4. \(f_q(v)\)를 최대화하고 \(f_q(v)\)를 최소화하는 loss를 최적화한다.

   \[l=-log\sigma (f_q(v))-log(1-\sigma(f_q(v')))\]

7. Split

쿼리의 정답과 오답 샘플을 그래프에서 나누는 방법은 아래와 같습니다.

Figure 17 : Query Templates

KG가 주어졌을때 Figure 17처럼 쿼리의 추상인 쿼리 템플릿의 정답 노드(ESR2)에서 반복적으로 시작하여 다른 edge와 node들이 모든 고정 노드에 도달할때까지 반복적으로 구체적인 엔티티와 관계의 모든 변수를 인스턴스화하여 쿼리를 생성합니다.

Figure 18 : (좌) 쿼리 템플릿 (우) 지식 그래프

1. 무작위로 지식그래프의 root 노드(Fulvestrant)에서 하나의 엔티티를 선택한다.
2. 엔티티의 집합의 교차합을 통해 정답 노드(Fulvestrant)를 가지는 두개의 집합을 얻게 됩니다.
3. 임의적으로 선택된 엔티티와 연관된 Projection edge를 인스턴스화(TreatedBy, CausedBy)한다.
4. 그 뒤로 anchor 노드(ESR2, Short of Breath)에 도달할때까지 연관된 projection edge로 가서 3번 절차를 반복한다.
5. ((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))) 쿼리를 인스턴스화 했다.

쿼리는 지식그래프에서의 답을 가지고 와야하며 답 중 하나는 answer node(Fulvestrant)를 인스턴스화합니다. 이러한 지식그래프에서의 탐색을 통해 모든 답의 집합(q : ((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))), a : Fulvestrant)을 얻어 오답(q : ((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))), a : Aspirin)을 샘플링 할 수 있습니다.

8. Visualization

이러한 박스 임베딩으로 아래와 같이 저차원으로 임베딩이 가능합니다.

Figure 19 : 현악기를 다룰 줄 아는 남자 연주자 리스트 t-SNE를 사용하여 임베딩 차원을 2차원으로 줄여서 쿼리 결과를 시각화한다.

1. Ren et al., Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings, ICLR 2020 ↩