CS224W - (11) Reasoning over Knowledge Graphs
Introduction
본 포스트에서는 지식 그래프 위에서 멀티홉 추론(multi-hop reasoning) 을 어떻게 수행하는지에 대해 다룹니다. 지식 그래프 위에서 추론의 종류는 다음과 같습니다.
- 멀티홉 쿼리에 대한 답변
- 경로 쿼리(Path queries)
- 결합 쿼리(Conjunctive queries)
- Query2Box
Example for KG: Biomedicine
위와 같은 지식 그래프가 있다고 가정하겠습니다. 이때 우리는 불완전하지만 거대한 지식 그래프에서 아래와 같은 멀티홉 추론, 즉 복잡한 쿼리에 대한 대답을 할 수 있을까요?
사실 지식 그래프 완성 문제는 원홉 쿼리(one-hop query)로 나타낼 수 있습니다. 지식 그래프 완성 태스크에서 $(h, r, t)$라는 링크가 존재하냐는 질문은 원홉 쿼리로 나타낸다면 쿼리 $(h, r)$의 답변이 $t$가 맞냐고 묻는 것과 같습니다. 그러면 이런 내용을 기반으로 멀티홉 추론에 대해서 알아보도록 하겠습니다.
멀티홉 추론
경로 쿼리(Path Queries)
어떤 경로에 더 많은 관계를 추가하여 원홉 쿼리를 경로 쿼리로 일반화할 수 있습니다. $n$-홉 경로 쿼리 $q$를 다음과 같이 표현할 수 있습니다.
\[q = (v_a, (r_1, \cdots, r_n))\]이때 $v_a$를 앵커 엔티티(anchor entity) 라고 부릅니다. 그리고 그래프 $G$에서 쿼리 $q$에 대한 답을 $⟦q⟧_G$라고 표기합니다.
경로 쿼리에 대한 쿼리 플랜은 위처럼 일종의 체인 형태입니다. 위에서 보여드린 그래프에서 ‘풀베스트란트(Fulvestrant)로 인한(caused) 부작용과 관련된(associated) 단백질은 무엇인가요?’라는 질문이 있다면 앵커 엔티티는 Fulvestrant, 그리고 관계 $r_1$, $r_2$는 각각 “Causes”와 “Assoc”가 됩니다. 결국 쿼리를 아까와 같이 표현하면 다음과 같습니다.
그러면 이 경로 쿼리에 대한 답은 어떻게 찾을 수 있을까요?
우선 지식 그래프에서 앵커 노드로부터 관계 “Causes”로 연결된 엔티티를 찾습니다. 위 그림처럼 총 네 개의 엔티티가 존재합니다. 그 다음 각 엔티티로부터 관계 “Assoc”으로 연결된 그 다음 엔티티를 찾으면 됩니다. 총 세 개의 엔티티를 답으로 얻을 수 있습니다.
이처럼 쿼리에 답을 하는 것은 단순히 그래프만 살펴보면 되는 쉬운 일처럼 보입니다. 하지만 지식 그래프는 일반적으로 완전하지 않고 모르는 부분이 많습니다. 엔티티 사이의 많은 관계가 이어져 있지 않거나 완전하지 않죠. 이런 불완전성 때문에 모든 쿼리에 대한 답이 되는 엔티티를 식별하기는 쉽지 않습니다. 바로 아래와 같은 경우입니다.
“Fulvestrant”에서 “short of Breath”로 이어지는 관계가 없으면 위 그림처럼 답을 찾을 수 없게 됩니다. 그렇다고 지식 그래프를 모두 완성 시킨 다음에 완전한 지식 그래프를 탐색하는 것도 방법이 될 수 없습니다. 완전한 지식 그래프를 만들게 되면 대부분의 $(h, r, t)$ 트리블렛이 0이 아닌 확률값을 갖게 되어 조밀한 그래프가 됩니다. 그렇게 되면 조밀한 지식 그래프에서의 탐색 시간은 경로 $L$에 대하여 지수적으로 증가하게 됩니다. 엄밀하게는 $O(d_\max^L)$ 만큼 말이죠.
그래서 우리는 불완전한 지식 그래프에 대한 경로 기반 쿼리에 답변할 수 있는 방법이 필요합니다. 이런 태스크를 예측 쿼리(predictive queries) 라고 합니다. 누락된 정보를 명시적이지 않게(implicitly) 추론하면서 임의의 쿼리에 답변하는 태스크입니다. 링크 예측 태스크의 일반화된 버전이라고 생각하시면 됩니다.
지식 그래프에서 예측 쿼리에 대한 답 찾기
경로 쿼리
일반적인 아이디어는 쿼리를 임베딩 공간에 매핑하고, 그 공간에서 추론을 학습하는 것입니다. 쿼리를 유클리드 공간의 단일 포인트에 임베딩을 하면 정답 노드가 쿼리에 가깝게 배치되는거죠. Query2Box는 단일 포인트가 아니라 어떤 박스 형태의 체(hyper-rectangular)로 매핑되고 정답 노드는 그 박스 안에 포함됩니다.
가장 중요한 요소는 역시 쿼리를 임베딩하는 것입니다. 멀티홉 추론을 위해서 지난 포스트에서 다룬 TransE를 일반화하는데요.
TransE는 다음의 스코어링 함수를 사용했습니다.
\[f_r(h, t) = -\| h + r - t \|\]이를 해석하는 다른 방법은 쿼리 임베딩이 $q = h + r$로 이루어진다는 것입니다. 위 그림처럼 앵커 노드에서 관계 $r$을 더했을 때 쿼리 임베딩이 나오게 됩니다.이제 목표는 쿼리 임베딩 $q$가 정답 임베딩인 $t$에 최대한 가까워지는 것입니다.
\[f_q(t) = -\|q - t \|\]그리고 TransE는 전이성(transitivity)을 만족하기 때문에 앵커 노드로부터 여러 개의 관계를 더할 수 있습니다. 참고로 TransE를 사용하는 이유는 TransR, DistMult, ComplEx 로는 전이성을 활용할 수 없기 때문입니다. 이 세 개의 방법론은 위처럼 앵커 노드로부터 관계의 합으로 정답 노드까지 찾아가는 과정을 수행할 수 없습니다.
임베딩 과정은 지식 그래프의 엔티티 수와 상관 없이 오직 벡터의 합으로만 진행합니다. 다음과 같이 위에서 다루었던 그래프를 아래와 같이 임베딩 과정을 통해 나타낼 수도 있습니다.
결합 쿼리(Conjunctive Queries)
로직을 결합하는 조금 더 복잡한 쿼리에는 어떻게 답할 수 있을까요? “호흡 곤란(Short of breath)을 유발하고(cause) 단백질 ESR2와 관련된(assoc) 질병을 치료하는(treated) 약물은 어떤 것이 있나요?”와 같은 긴 쿼리가 있습니다. 이걸 쿼리 플랜으로 나타내면 다음과 같습니다.
두 엔티티를 앵커 노드로 하고 각 앵커 노드에서 관계를 합한 다음 마지막 노드에서 교집합에 속하는 노드만을 정답으로 꼽습니다. 위 플랜을 실제 그래프에 적용 시키면 다음과 같습니다.
우선 ESR2와 Assoc 관계에 있는 노드는 Lung Cancer와 Breast Cancer입니다. 각 노드에서 TreatedBy 관계에 있는 노드는 Paclitaxel, Arimidex, Fulvestrant입니다. 이제 두 번째로 Short of Breath와 CausedBy 관계로 있는 노드는 Paclitaxel, Fulvestrant, Ketamin입니다. 따라서 정답은 Paclitaxel과 Fulvestrant입니다.
그런데 여기서 ESR2에서 Breast Cancer로 가는 관계가 지식 그래프에 없다면 어떻게 될까요? 분명 Fulvestrant까지 탐색하지 못하기 때문에 정답이 바뀌게 되겠죠.
그러면 우리는 어떻게 임베딩을 사용해서 미싱 링크를 채워넣을 수 있을까요? 다시 그래프를 잘 살펴보시면 ESR2 는 BRCA1, ESR1과 상호작용을 하고 두 단백질은 모두 Breast Cancer와 관련(Assoc)이 있습니다. 그러면 이런 중간 노드들이 엔티티의 집합으로 나타나는데 어떻게 표현할 수 있을까요? 그리고 잠재 공간(latent space)에서 교집합 연산은 어떻게 가능할까요?
Query2Box
우선 쿼리를 박스에 임베딩하는 박스 임베딩(box embedding) 에 대해서 알아보도록 하겠습니다. 위 그림은 “Fulvestrant”의 부작용을 임베딩한 결과이고, 답이 되는 엔티티를 하나의 박스가 감싸고 있습니다. 중심이 되는 $q$에 대해서 박스 임베딩은 다음과 같습니다.
\[\mathbf{q} = (\text{Center}(q), \text{Offset}(q))\]박스간 교집합을 찾는 것은 그래도 쉬운 일입니다. 지식 그래프를 탐색하며 답을 찾을 때 각 단계는 도달 가능한 엔티티의 집합을 생성합니다. 박스들은 매우 추상화된 결과물입니다. 우리가 중심을 정하고 엔티티의 집합을 둘러싸는 박스를 모델링하기 위해 오프셋을 잘 설정하기만 하면 되기 때문이죠.
이제 우리가 찾아야 하는 것은 다음과 같습니다.
- 엔티티 임베딩 (파라미터 수: $d|V|$)
- 엔티티는 부피가 0인 박스로 나타냅니다.
- 관계 임베딩 (파라미터 수: $2d|R|$)
- 각 관계가 하나의 박스를 갖고 새로운 박스를 생성합니다.
- 관계의 개수와 중심값, 오프셋만큼의 파라미터가 있습니다.
- 교집합 오퍼레이터 $f$
- 박스를 입력으로 받고 박스를 반환하는 새로운 오퍼레이터입니다.
- 직관적으로 박스의 교집합을 모델링합니다.
위 쿼리의 답을 찾기 위해 앵커 노드인 “ESR2”와 “Short of Breath”로부터 지식 그래프를 탐색한다고 가정을 하겠습니다.
Projection Operator
위에서 언급하였듯이 엔티티 임베딩도 부피가 0인 박스입니다. 이 박스를 다른 엔티티들을 포함하는 어떠한 박스로 확장해야 하는데 여기서 프로젝션 오퍼레이터(Projection Operator) 를 사용합니다. 프로젝션 오퍼레이터 $\mathcal{P}$를 다음과 같이 정의합니다.
\[\mathcal{P}: \text{Box $\times$ Relation $\rightarrow$ Box}\] \[\begin{aligned} \text{Cen}(\mathbf{q}^\prime) &= \text{Cen}(\mathbf{q}) + \text{Cen}(r) \\ \text{Off}(\mathbf{q}^\prime) &= \text{Off}(\mathbf{q}) + \text{Off}(r) \end{aligned}\]
프로젝션 오퍼레이터를 이용하면 위와 같이 엔티티로부터 임베딩 스페이스에 하나의 박스를 생성하게 됩니다.
계속해서 쿼리 플랜에 따라서 임베딩 스페이스에서 박스를 확장해나갑니다.
마지막으로 다른 엔티티로부터 관계를 프로젝션 오퍼레이터를 통해 박스를 확장하여 임베딩 공간에 생성합니다. 그럼 여기서 초록색 박스와 노란색 박스의 교집합을 구하면 되는데 어떻게 구할 수 있을까요?
교집합 찾기
이번엔 기하 교집합 오퍼레이터(Geometric Intersection Operator) $\mathcal{J}$ 를 도입합니다. 이 오퍼레이터는 여러 개의 박스를 입력으로 받은 후 교집합 박스를 반환합니다. 기하 교집합 오퍼레이터의 핵심 아이디어는 새로 생길 교집합 박스의 중심이 입력으로 받은 여러 개의 박스의 중심에 가까워야 하고, 교집합 박스의 크기는 모든 박스의 크기보다는 작다는 점입니다.
\[\mathcal{J}: \text{Box $\times$ Box $\times \cdots \times$ Box} \rightarrow \text{Box}\]
새로운 교집합 박스의 중심은 다음과 같이 구합니다.
\[\text{Cen}(q_\text{inter}) = \sum_i w_i \odot \text{Cen}(q_i)\] \[w_i = \frac{\exp(f_\text{cen}(\text{Cen}(q_i)))}{\sum_j \exp(f_\text{cen}(\text{Cen}(q_j)))}\]새로운 교집합 박스의 중심은 위 그림에서 반드시 빨간 사각형 안에 위치해야 합니다. 따라서 중심점은 입력으로 받은 박스의 중심에 대해 가중합을 통해 얻어낼 수 있습니다. $w_i \in \mathbb{R}^d$ 는 뉴럴넷인 $f_\text{cen}$으로 계산되는데, $w_i$는 각 입력 박스의 중심점인 $\text{Cen}(q_i)$에 대한 “self-attention”을 나타냅니다.
교집합 박스의 크기는 다음과 같이 구합니다.
\[\text{Off}(q_\text{inter}) = \min(\text{Off}(q_1), \cdots, \text{Off}(q_n)) \odot \sigma (f_\text{off}(\text{Off}(q_1), \cdots, \text{Off}(q_n)))\]첫 항을 통해서 교집합 박스의 크기를 입력 박스의 크기보다 작도록 보장받음을 알 수 있습니다. 또한 $\sigma$는 시그모이드로 뒤 항의 값을 0에서 1사이로 줄여줍니다. $f_\text{off}$은 표현력을 높이기 위해 입력 박스들의 표현을 추출하는 뉴럴넷입니다. 우리는 이처럼 두 가지 오퍼레이터를 이용해서 아래와 같이 답이 포함된 교집합 박스를 얻어낼 수 있습니다.
그러면 어떤 엔티티로부터 박스의 중심까지의 거리는 어떻게 계산할까요? 당연히 엔티티와 박스의 중심까지 거리는 가까울 수록 좋을텐데요. 스코어링 함수 $f_q(v)$가 있을 때 이 함수는 정답인 노드 $v$로부터 쿼리 $q$까지의 거리의 음수가 됩니다. 주어진 쿼리 박스 $\mathbf{q}$와 엔티티 임베딩 $\mathbf{v}$가 있을 때 $\mathbf{q}$와 $\mathbf{v}$ 사이의 거리는 다음과 같이 구합니다.
만약 어떤 점이 상자로 둘러싸여 있으면 거리의 가중치를 낮추게 됩니다. 최종적인 스코어링 함수는 다음과 같습니다.
\[f_q(\mathbf{v}) = -d_\text{box}(\mathbf{q}, \mathbf{v})\]합집합 찾기
교집합은 일단락 되었는데 합집합은 어떻게 찾을 수 있을까요? 다음과 같이 합 연산을 포함한 복잡한 쿼리의 임베딩은 어떻게 해야할까요?
유방암이나 폐암을 치료할 수 있는 약물은 무엇인가?
결합 쿼리와 합집합(disjunction)을 합친 것을 Existential Positive First-order (EPFO) 라고 부릅니다. CS224W 강의에서는 편의상 AND-OR 쿼리라고 부릅니다. 그러면 우리는 교집합에서 했던 것처럼 AND-OR 쿼리를 저차원의 벡터 공간에 임베딩할 수 있을까요?
세 개의 쿼리 $q_1, q_2, q_3$가 있고 각 정답이 있다고 가정하겠습니다.
\[⟦q_1⟧ = \{v_1\}, ⟦q_2⟧ = \{v_2\}, ⟦q_3⟧ = \{v_3\}\]만약 우리가 합집합 연산을 한다고 했을 때 2차원 공간에 임베딩할 수 있을까요?
세 개의 정답 엔티티에 대해 합집합 연산은 가능합니다. 하지만 여기에서 엔티티가 하나 더 늘어나게 되면 문제가 발생합니다.
위 그림처럼 $\mathbf{v}_2$ 와 $\mathbf{v}_4$를 합집합 형태로 하나의 박스로 묶으면 반드시 $\mathbf{v}_3$이 들어가는 형태가 되기 때문입니다. 결론적으로 $M$ 개의 겹치지 않는 결합 쿼리 $q_1, q_2, \cdots, q_M$ 이 주어졌을 때 공간의 차원은 $\Theta(M)$이 되어야 OR 쿼리를 다룰 수 있습니다.
그래서 다른 방법을 사용해야 합니다. 합집합 연산이 있는 쿼리 플랜을 조금 비틀어서 모든 합집합 연산을 제거하고 마지막 단계에서만 합집합 연산을 하는거죠.
이처럼 어떤 AND-OR 쿼리라도 선언표준형(Disjunctive Normal Form) 으로 변환할 수 있습니다. 주어진 어떤 AND-OR 쿼리 $q$에 대해서 $m$ 개의 결합 쿼리가 있을 때 다음과 같이 나타낼 수 있습니다.
\[q = q_1 \vee q_2 \vee \cdots \vee q_m\]이때 각 엔티티는 임베딩 공간에서 정답 쿼리인 $\mathbf{q}$에 가까워야 합니다. 따라서 정답 쿼리인 $\mathbf{q}$와 엔티티 사이의 거리는 다음과 같이 정의합니다.
\[d_\text{box}(\mathbf{q}, \mathbf{v}) = \min(d_\text{box}(\mathbf{q}_1, \mathbf{v}), \cdots, d_\text{box}(\mathbf{q}_m, \mathbf{v}))\]AND-OR 쿼리 $\mathbf{q}$를 임베딩하는 과정은 다음과 같습니다.
- 쿼리 $q$를 동등한 선언표준형 $q_1 \vee q_2 \vee \cdots \vee q_m$으로 변형합니다.
- $q_1$부터 $q_m$까지 임베딩합니다.
- 거리 $d_\text{box}(\mathbf{q}_i, \mathbf{v})$를 계산합니다.
- 모든 거리의 최솟값을 구합니다.
- 최종 스코어 $f_q(v) = -d_\text{box}(\mathbf{q}, \mathbf{v})$를 계산합니다.
Query2Box 학습하기
Query2Box를 학습하는 방법은 지식 그래프를 완성하는 것과 비슷합니다. 주어진 쿼리 임베딩 $\mathbf{q}$ 에 대하여 정답 엔티티 $v \in ⟦q⟧ $ 에 대한 스코어 $f_q(v)$ 를 최대화하고 정답이 아닌 엔티티 $v^\prime \in ⟦q⟧ $ 에 대한 스코어 $f_q(v^\prime)$ 을 최소화합니다. 학습 가능한 파라미터는 위에서 다룬 바 있습니다.
- $d |V |$ 개 파라미터를 가진 엔티티 임베딩
- $2d |R|$ 개 파라미터를 가진 관계 임베딩
- 교집합 오퍼레이터
Query2Box의 자세한 학습 과정은 다음과 같습니다.
- 학습 그래프 $G_\text{train}$으로부터 쿼리 $q$, 정답 엔티티 $v \in ⟦q⟧_{G_\text{train}}$, 정답이 아닌 엔티티 $v^\prime \not\in ⟦q⟧_{G_\text{train}}$을 샘플링합니다.
- 쿼리 $\mathbf{q}$를 임베딩합니다.
- 현재 오퍼레이터를 이용해서 임베딩합니다.
- $f_q(v)$와 $f_q(v^\prime)$을 계산합니다.
- 임베딩과 오퍼레이터를 손실 함수 $\ell$를 최소화하여 최적화합니다.
Query templates
복잡한 쿼리는 위처럼 쿼리 템플릿으로부터 시작합니다. 쿼리 템플릿이란 일반적인 쿼리의 추상화된 버전입니다. 이제 지식 그래프의 구체적인 엔티티와 관계로부터 모든 변수를 인스턴스화하여 쿼리를 생성합니다.
위 그림을 예로 들자면 Anchor1 엔티티를 “ESR2”로, Rel1 관계는 “Assoc”로 인스턴스화합니다. 그러면 주어진 그래프를 쿼리 템플릿으로 어떻게 인스턴스화할 수 있을까요? 우선 쿼리 템플릿의 정답 노드를 인스턴스화하는 것부터 시작합니다. 그 다음 다른 엣지나 노드를 인스턴스화하면서 앵커 노드까지 인스턴스화를 진행합니다.
위 그래프를 예로 들어보면 왼쪽 쿼리 템플릿의 루트 노드로 “Fulvestrant”를 선택했다고 가정해보겠습니다. 그 다음 교집합을 살펴보면 엔티티의 교집합이 “Fulvestrant”이기 때문에 두 집합에도 당연히 “Fulvestrant”가 포함됩니다.
그 다음 “Fulvestrant”와 연결된 하나의 관계를 무작위로 샘플링하여 템플릿에 있는 프로젝션 엣지를 인스턴스화합니다. 예를 들어 관계 “TreatedBy”를 선택하고 어떤 엔티티가 “TreatedBy” 관계로 “Fulvestrant”와 연결되어 있는지 확인할 수 있습니다. 위 그림에 따르면 “Breast Cancer” 엔티티와 연결되어 있습니다.
그리고 프로젝션 엣지를 “Breast Cancer”와 관련이 있는 관계(“Assoc”)를 통해 마지막 엔티티로 이동합니다. 위 그래프에 따르면 “ESR2” 엔티티입니다. 아래 노란색 프로젝션 엣지도 비슷한 방법으로 “CausedBy” 관계를 통해 “Short of Breath” 엔티티와 연결되는 것을 확인할 수 있습니다.
복잡한 쿼리를 인스턴스화하기 위해서는 지식 그래프에 정답이 존재해야 하며, 정답 중 하나가 인스턴스화되어 있어야 합니다. 위 그래프에서는 “Fulvestrant” 엔티티가 인스턴스화되어 있어야 하죠. 지식 그래프 탐색을 통해 전체 정답 집합인 $⟦q⟧_G$를 얻을 수도 있고, 정답이 아닌 엔티티인 $v^\prime \not\in ⟦q⟧_G$를 샘플링할 수도 있습니다.
위 그림은 쿼리 결과를 시각화하기 위해 t-SNE를 이용해 임베딩 공간을 2차원으로 차원 축소한 것입니다. “현악기를 연주하는 남성 연주자 목록”이라는 쿼리에 대해서 다음과 같은 결과를 얻을 수 있습니다.
