知识图谱补全任务与一种基于Embedding的知识图谱补全模型
知识图谱补全任务是指基于现有知识图谱，找出其中可能存在的潜在关系；TransE是一种基于Embedding的知识图谱补全模型。
知识图谱补全任务与模型
知识图谱补全
问题定义
知识图谱补全问题，是指在给定原始知识图谱的前提下，找出在原图谱中不存在，但实际存在的潜在关系，该问题同样可以看作一个有向异质图上的链接预测问题，也即利用当前网络已观测到的链接，预测当前网络暂未观测到（遗失的或未来可能出现的）的链接。
这一问题可建模为如下形式：
- 输入：原始知识图谱$(G=(V,E)$)
- $(G$)：一般是一个有向连通图
- $(V$)：图谱中实体的集合
- $(E$)：图谱中所有关系的集合
- 输出：关系集合$E^\prime; \forall e\in E^\prime, e_h \in V, e_t\in V, e\notin E$
- $(e_h$)：关系中的头实体
- $(e_t$)：关系中的尾实体
- $(e_r$)：关系类型
则对于知识图谱补全这一问题，我们可以由原始知识图谱$(G$)得到一个候选关系集合$(E^{\prime\prime}$)，该集合：
- $E^{\prime\prime}=\{e|e_h\in V, e_t\in V, e\notin E\}$
- $E^\prime \sub E^{\prime\prime}$
- $E^{\prime\prime}$同样可以是一个人为定义的、规模更小的集合
对于知识图谱补全问题，我们可以将其看作是一个对$E^{\prime\prime}$中元素的判定（二分类）问题
- 解决这一类问题的本质思路是寻求一个打分模型，用于评估$E^{\prime\prime}$中每一条关系三元组真实存在的置信度：
- 即$\operatorname{score} (e), e\in E^{\prime\prime}$
- 打分完毕后，应按$E^{\prime\prime}$中关系存在的置信度从高到低进行排序
问题目标
按照上文中对于问题的定义，我们可以将上文中提到的候选关系集合$(E^{\prime\prime}$)分为两部分：
- $E^{\prime\prime}$中实际存在的关系三元组为正样本，构成集合$S$
- $E^{\prime\prime}$中实际不存在的关系三元组为正样本，构成集合$S^\prime$
对于知识图谱补全问题而言，最理想的状况就是：
$$ \forall s \in S, s^{\prime} \in S^{\prime}, \quad \operatorname{score}>\operatorname{score}\left(s^{\prime}\right) $$
验证与评估
但对于知识图谱而言，又存在另一个问题，知识图谱中动辄上万上十万的节点数量，导致候选关系集合$(E^{\prime\prime}$)规模极为庞大。例如对于一个拥有$n$个实体的知识图谱，其中可能存在的链接（即边）有$n^2$个，如果再考虑关系类型（即边的种类），可能存在的三元组数量就变为了$mn^2$，其中$m$为关系类型的数量，而由于知识图谱中的链接通常而言较为稀疏，因此候选关系集合$(E^{\prime\prime}$)规模可以约等于$mn^2$。对于这个规模级别的排序问题，无论采取何种排序算法，最终的复杂度都不会低于$O(mn^2\log{mn^2})$，这个计算代价几乎是不可承受的。
显然，对于这类问题的评估方案不能直接地使用所有可能存在的链接作为候选关系集合$(E^{\prime\prime}$)，否则该问题的评估代价将高到不可接受。
那么应当如何对这一类问题进行合适的评估呢？对于一个真实存在的关系三元组$(h,r,t)$而言，显然当我们固定头实体$h$与关系类型$r$时，候选的尾实体数量将会将为$n$。对于这样一个规模的候选关系集合而言，排序的代价是完全可以接受的，因此，我们可以将所有可能存在的链接划分为$k$份，并对每一份分别进行评估，最后总的评估结果通常而言是对$k$个候选关系子集的评估结果进行平均，其中$k=mn$。
常见指标：
- MR(Mean Rank)：正样本集合$S$中的元素在$E^{\prime\prime}$中所有元素中的按置信度得分的排位的均值
- MRR(Mean Reverse Rank)：正样本集合$S$中的元素在$E^{\prime\prime}$中所有元素中的按置信度得分的排位的倒数的均值
- hit@N: 在$E^{\prime\prime}$中所有元素中的按置信度得分由高到低排位后前 N 位的元素所形成的集合与正样本集合$S$是否有交集，有交集则为1，否则为0。
知识图谱表征与补全模型
知识图谱及其表征
知识图谱是一种由实体（节点）和多种不同类型的关系（边）组成的多关系图，其中关系常被表示为三元组的形式，这种关系三元组又被称为事实。对于关系三元组，其组成形式为(头实体，关系类型，尾实体)，例如对于实体“柏拉图”和“苏格拉底”，它们之间存在类型为“老师”的关系，则这一条关系可被记为(“柏拉图”，“老师”，“苏格拉底”)。通过这种三元组的表达形式，知识图谱中地结构化数据得以高效地表达并应用于下游任务中。
尽管关系三元组的表达形式足够直观与高效，但近年来的知识图谱关系补全技术的研究更聚焦于基于知识图谱嵌入这一表达形式。这一表达形式的核心思想在于将知识图谱中所包含的实体与关系类型嵌入到一个连续的向量空间中，为知识图谱中的实体与关系类型生成一个合适的向量表示（即 Embedding 向量），然后在所形成的嵌入空间中，进行知识图谱的关系补全。
基于Embedding嵌入的知识图谱补全模型
显然，对于基于知识图谱嵌入的知识图谱关系补全的核心要点在于如何获得合适的知识图谱嵌入。目前，大多数知识图谱嵌入技术使用知识图谱中的关系三元组来获取合适的 Embedding，在这一过程中，通常会强制 Embedding 在打分函数上的表现与知识图谱中所存在的事实相符。典型的知识图谱嵌入技术通常包含三个步骤：
- 对实体和关系类型进行表征
- 定义打分函数(score function)
- 对实体和关系技术的Embedding进行学习和优化
第一步中，需要对实体与关系嵌入到连续向量空间的形式进行确定，通常以向量的形式对实体进行表征，而关系则往往被看作是在向量空间中的运算过程，常用向量、矩阵、张量等形式进行表征。第二步的目的在于定义一个衡量关系三元组好坏程度的打分函数$𝑓(ℎ, 𝑟, 𝑡)$，其中$h,r,t$分别为关系三元组中头实体、关系类型和尾实体对应的在连续向量空间中的表示。在打分函数中，知识图谱中存在的关系三元组应当比图谱中不存在的关系三元组获得更高的分数。最后一步就是求解一个使得知识图谱中所有存在的关系三元组的总似然(likelihood)最大化的最优化问题。
TransE模型
TransE模型是一种典型的基于嵌入的知识图谱补全模型，其将关系建模为在嵌入空间中的平移。通过头实体对应的 Embedding 向量在经过关系类型对应的 Embedding 向量的平移后，与尾实体对应的 Embedding 向量的距离来估计该关系三元组存在的可能性。
如上图所示，TransE 模型将知识图谱中的实体和关系类型表征为同一向量空间中的向量表示，并认为在理想情况下，头实体对应的 Embedding 向量在经过关系类型对应的 Embedding 向量的平移后应当与尾实体对应的 Embedding 向量相等。即，对于任意真实存在的关系三元组$(h,r,t)$，其对应的 TransE 模型中的 Embedding 向量分别为$\bm{h,r,t}$，则在理想情况下，$\bm{h+r=t}$始终成立。基于这一理想情况，TransE 模型设计出的打分函数为：$f(h,r,t)=-\left\Vert\bm{h+r-t} \right\Vert_{1/2}$，拥有更高得分的三元组在模型看来更可能实际存在。在确定实体和关系类型的表征与打分函数后，还需要对模型进行训练，TransE 模型的训练目标基于两个集合，正样本集合$S$和负样本集合$S^\prime$，其中正样本集合𝑆𝑆中包含知识图谱中真实存在的关系三元组，负样本集合$S^\prime$中包含知识图谱中实际不存在的关系。训练目标为$\min \Sigma_{(h,r,t)\in S}\Sigma_{(h^\prime,r^\prime,t^\prime)\in S^\prime[\gamma-f(h,r,t)+f(h^\prime,r^\prime,t^\prime)]_{+}}$。基于此训练目标，TransE模型使用梯度下降法对实体与关系类型的 Embedding 向量进行优化。