简介
题目：《Bootstrapping Entity Alignment with Knowledge Graph Embedding》
来源：IJCAI-2018
链接：论文链接
代码：Code和Dataset
关键字：Entity Alignment、Bootstrapping、Embedding
研究背景
近些年（基于2018年的），一些基于Embedding的实体对齐方法被提出，虽然取得了不错的效果，但是仍存在一些问题：
1) KG Embedding部分主要复用面向KG补全的Embedding模型，面向实体对齐的Embedding模型有待探索。
2)在训练数据比较少的情况下，当前方法精度很低。
为此我们提出了一个Bootstrapping的方法，将实体对齐转化为一个分类问题，期望学习的Embeddings具有最大的实体对齐似然。具体地，我们提出了一个面向实体对齐的KG Embedding模型(AlignE)；然后动态标记新的实体对齐作为训练数据来增强匹配效果(BootEA)。
Problem Formulation
$X$ 与 $Y$ 分别表示 $KG_1$ 和 $KG_2$ 的实体集合，实体对齐任务就是去寻找 $A = {(x,y) \in X\times Y|x \sim_R,y}$ 不同 $KG$ 中的等价的实体对。作者将其任务定义为一个分类任务，即用 $Y$ 中的实体去给 $X$ 中的实体进行贴标签。不过这里和一般的分类任务不一样，这里的实体标签只能一对一，即一个$Y$实体标签只能给一个实体$X$进行标注，或者不标签，这里作者使用 $\Theta$ 表示不同的 $KG$ 的嵌入表示，其中 $y\in Y$ 作为标签，$x \in X$ 作为待标注的实体，其对于某个实体 $x$ 对应是标签 $y$ 的概率如下公式：
$$
\pi(y|x;\Theta) = \sigma(sim(\overset{\rightarrow}{v}(x),\overset{\rightarrow}{v}(y))) \tag {1}
$$
其采用向量的第二范式距离，然后用激活函数转换表示标签的准确性概率的大小，然后作者采用选取全局整体的标签准确率之和最大的情况，其中的 ${\mathbb{L}x}$ 表示实体 $x$ 正确的标签，而指示函数 $1{[\cdot]}$的取值为$(0,or,1)$:
$$
\begin{aligned}
\hat\Theta &= \arg\max_{\Theta}\sum_{x\in X}\log \pi(\mathbb{L}x |x;\Theta) \ &=\arg\max{\Theta}\sum_{x\in X}\sum_{y\in Y}1_{[y=\mathbb{L}_x]}\log \pi(y |x;\Theta)
\end{aligned}
\tag {2}
$$
上式中考虑的重点在于对齐的实体对的相似概率，而对于其他没对齐的实体的信息没保留，所以这个方程式对于实体对齐不太好，后续的目标函数也是处于这样的考虑的。
Methodology
Alignment-Oriented KG Embedding
作者本文将两个 $KG$ 的实体编码在统一空间中，这样就可以直接计算实体之间的相似性。作者采用Translation-based Model去捕获语义信息，即评价函数为：$f(\tau) = ||\overset{\rightarrow}{v}(h)+\overset{\rightarrow}{v}(r)-\overset{\rightarrow}{v}(t)||^{2}{2}$ ，用来表示三元组$\tau = (h,r,t)$ 的可能性，采用Margin-based Ranking Loss的损失函数虽然是保证正实例之间的距离能够小与负样本之间的距离，但是[Zhou etal., 2017]文中研究发现，这个函数不能保证正样例的距离足够小，即表示的之间的可能性不准确，所以作者提出了一种新的损失函数：
$$
O{e}=\sum_{\tau\in\mathbb{T}^{+}}[f(\tau)-\gamma_{1}]{+}+\mu{1}\sum_{\tau^{\prime}\in\mathbb{T}^{-}}[\gamma_{2}- f(\tau^{\prime})]{+} \tag {3}
$$
其中$[\cdot]{+}=\max(\cdot,0),\gamma_{1},and,\gamma_{2} > 0,\mu_{1}>0$，而对应的 $\mathbb{T}^{+}和 ,\mathbb{T}^{-}$ 分别表示正负样本集合。该方程式有两个特性：1-该方程可以保证正确的实体对能维持更小的距离值，同时保证负样本能后具有更大的距离值，这里设定 $\gamma_{2}>\gamma_{1}$；同时能够保证$f(\tau^{\prime})-f(\tau)\ge\gamma_{2} -\gamma_{1}$，这个也保留了原先的Margin-based Ranking Loss的特性。
$\epsilon$-Truncated Uniform Negative Sampling
一般生成负样例的方法就是随机的替换关系中的头结点或者尾结点，但是这样的替换可能与原先的关系组很容易区分，即差别太大了，对于嵌入式的学习来说可能影响不大，作者本文中希望能识别出很近关系组之间的区别，作者对实体 $x$ 的替换选择如下：选择离其最近的 $s$ 个实体，其中$s= \left\lceil (1-\epsilon)N\right\rceil,\epsilon\in[0,1)$ ，$N$ 是 $KG$ 中的实体的数目，$\left\lceil \cdot\right\rceil$是向上取值函数，取代的实体将和原先的实体非常相似，这样对训练更有帮助。
Parameter Swapping
作者通过扩增三元组的同时将两个图谱在同一空间进行嵌入学习，对于对齐的实体对$(x,y)\in A^{\prime}$ ，通过替换对应的实体来增加对齐的三元组：
$$
\mathbb{T}^{s}{(x,y)} = {(y,r,t)|(x,r,t)\in\mathbb{T}^{+}{1}}\cup{ (h,r,y)|(h,r,x)\in\mathbb{T}^{+}{1}}\cup {(x,r,t)|(y,r,t)\in\mathbb{T}^{+}{2}} \cup{(h,r,x)|(h,r,y)\in\mathbb{T}^{+}_{2}} \tag {4}
$$
然后作者根据产生的正样例再分别按照上诉方法取负样例。注意是这种替换可能增加了某个图中没有的关系三元组，丰富了关系组合。
Bootstrapping Alignment
嵌入表达学习由于缺少对齐的实体对，作者通过迭代不断的增加对齐的实体对，从而提升对齐的性能。作者将具有较高可信度的实体对加入到已知对齐的实体对中间去，作为训练数据。
Likely Alignment Labeling and Editing
传统的Bootstrapping方法每次都是选取最可信的标签去标签数据，但是本研究中标签的数据是受限的，就是一对一的关系，就是一个标签使用以后就不能标签其他实体了，作者由此提出了其下面优化的目标函数：
$$
\max \sum_{x\in X^{\prime}}\sum_{y\in Y^{\prime}{x}}\pi(y|x;\Theta^{(t)}\cdot\psi^{(t)}(x,y)) \
s.t.\sum{x^{\prime}\in X^{\prime}}\psi^{(t)}(x^{\prime},y)\le1,\sum_{y^{\prime}\in Y^{\prime}{x}}\psi^{(t)}(x,y^{\prime})\le1,\forall x,y \tag {5}
$$
其中的 $\Theta^{(t)}$ 表示第 $t$ 次迭代时候的嵌入表达向量，$Y^{\prime}{x} = {y|y\in Y^{\prime} and,\pi(y|x;\Theta^{(t)})\gt\gamma_{3}}$ 表示实体 $x$ 的候选实体集，$\psi^{(t)}{(\cdot)}$ 就是一个指示函数，如果实体 $x$ 被 $y$ 贴上标签，那么值就为1，否则就为0。上面两个不等式保证了一对一的关系，不会存在一个标签重复使用的情况。每次迭代后，作者将新加的实体对增加到训练数据中去，继续后续的训练。
随着时间的递增，训练效果应该越来越好，但是任然会产生误差，为了去缓解这种误差的影响，在该训练中，对于一个已经被贴新标签的实体，在后续的训练中，可以被取消标签或者替换新的标签，这样的方法在本次研究中心，既简单有有效，在判断标签是否有效的时候，是通过比较其距离的大小，如下式：
$$
\triangle^{(t)}_{(x,y,y^{\prime})} = \pi(y|x;\Theta^{(t)})-\pi(y^{\prime}|x;\Theta^{(t)}) \tag {6}
$$
Learning from Holistic Perspective
为了获取一个全局的已标签或未标签的情况，对其定义了以下的分布（7），如果被标记了，那么其对应的概率为1（只有y等于真正标签的时候），没有被标记的话就是一个均匀分布（和总体的未标记的数目有关），然后给定该概率分布后，得到新的对齐目标函数（求其最小值）：
$$
\phi_{x}(y)=\left{
\begin{aligned}
1_{[y=\hat{y}]} & = &if,x, is , labeled,as,\hat{y} \
\frac{1}{|Y^{\prime}|} & = &if,x, is , unlabeled
\end{aligned}
\right.
\tag {7}
$$
$$
O_{a}=-\sum_{x\in X}\sum_{y\in Y}\phi_{X}(y)\log\pi(y|x;\Theta) \tag {8}
$$
最后作者整体考虑，其最终的目标函数如下：
$$
O=Q_{e}+\mu_{2}\cdot Q_{A} \tag {9}
$$
Implementation Details
本部分主要是对参数的具体说明，详见论文。
实验分析
本文作者采用了DBP15K和DWY100K两类数据集，其中后面一个数据集的详情如下：
其中对照的模型以及对其的实验结果如下图：
其结果可以看出其结果优于当其先提出的模型，而且在性能上面有较大的提升。
结果分析
作者为了说明其性能的优越性的原因，分别对以下4各方面进行对照实验：
- Effectiveness of $\epsilon$-Truncated Uniform Negative Sampling
- Accuracy of Likely Alignment
- Sensitivity to Proportion of Prior Alignment
- F1-score w.r.t. Distribution of Relation Triple Numbers
作者通过其上面的实验，进一步说明其提出的相关策略的有效性，其具体的分析可以见原文，里面介绍很详细。