简介
题目：《A Benchmarking Study of Embedding-based Entity Alignment for Knowledge Graphs》
来源：VLDB-2020
链接：论文链接
代码：Code和Dataset
关键字：Benchmarking Study、Embedding-based、Entity Alignment
Abstract
这篇文章主要对实体对齐该领域进行了一次综合性的分析研究，调研了23种Embedding-based的实体对齐方法，并根据其使用的技术和特性进行分类；作者提出了一种新的取样的方法，其可以保证其取样和现实数据集分布一致；同时构建了一个开源库-OpenEA，其包含了12种具有代表性的基于嵌入学习的实体对齐方法，以及对这些技术的评估方法；最后作者在一些还没被探索的方向进行了一些探索实验的分析研究。整体来说，本文章对基于嵌入学习的实体对齐的方法技术进行了一次综述分析。
Introduction
知识图谱（KG）一般以三元组形式存储事实，一般分为两类：(subject entity, relation, object entity) 和(subject entity,attribute, literal value)。传统的方法一般会利用很多实体的特征，如名称、描述性注释、关系结构等，而对齐的难点一般在于相互独立创建的KGs之间符号、语言和结构异构性。
Embedding-based的实体对齐的方法最近几年快速发展，这个方法是基于KG嵌入技术的，其将”符号“（即实体或者关系等）表示成向量空间的低纬向量，其蕴含的语义信息则通过其在空间中的几何特性（如空间距离）来表示。如上图所示的基于嵌入式的实体对齐模型结构。通过对种子实体对和KGs进行训练，学习其KGs之间的联系。而对于嵌入模型与对齐模型之间的交互通常有两种方式：一种是通过种子对进行学习一个KG到另一个KG的映射矩阵，第二种是将KGs嵌入学习到同一空间中，这个通过保证种子对实体尽可能有相似的嵌入表示来实现的。然后通过判断实体的嵌入式表达来判断相似度，进而实现实体对齐。但处于研究热点的该方向，依然有很多问题：
- 缺少相关的现状总结分析
- 缺少相关公认的用来评价实体对齐的基准数据集
- 相应的研究方法代码开源较少
本文就针对相关的问题，作者进行相关研究分析，其主要类容如下：1）一个广泛综合的调研；2）基准的数据集；3）相关开源库；4）综合的比较分析；5）探索性实验；6）未来展望。
Preliminaries
实体对齐任务就是在两个KGs之间寻找一对一的实体对，一般情况下会有一些预先知道的实体对作为训练数据进行训练模型。
Literature Review
Knowledge Graph Embedding
Approaches
目前存在的嵌入学习模型大致可以分成三大类：1）$translational,,models$ ；2）$semantic,,matching,,models$；3）$deep,,models$ 。这些模型大多都用于实体链接。
Datasets & Evaluation Metrics
FB15K和WN18都是两个用于实体链接的基准数据集，由于测试集的泄露问题分别新建了两个对应的数据集FB15K-237和WN18RR。三个评价标准如下：1）top-m ranked（Hits@m，就是在排名前m名之内所占的比例）；2）mean rank (MR) of correct links；3）mean reciprocal rank (MRR)
Conventional Entity Alignment
Approaches
一种是基于OWL语义的等价性推理方法，另一种是基于相似计算的方法，近几年还有用统计机器学习和众包来提升准确性。其实体对齐的相关研究主要依赖于实体的文本信息。
Datasets & Evaluation Metrics
自从2004年起，OAEI(Ontology Alignment Evaluation Initiatives)成为本体对齐（Ontology Alignment）的主要标准，对实体对齐这方向也有设计了的评价标准，但是基于嵌入式实体对齐方法好像都没使用该评价标准，其标准主要是准确率，召回率和F1值。
Embedding-based Entity Alignment
Approaches
大多存在方法都是使用基于关系三元组的Translational Models，近年来发展了Graph Convolutional Networks (GCNs)的模型，除此之外，还有一些方法尝试整合属性以及值的嵌入表达，一些网络对齐或跨语言的知识的引入方法也有人在实体对齐方法尝试。
Datasets & Evaluation Metrics
其没有公认的数据集进行评价，一般有DBP15K和WK3L。如下图展示了其度的分布情况以及和真实KGs之间的差异。而评价标准和实体链接类似，Hits@m，MR，MRR。
Categorization of Techniques
表一展示23类近年来基于嵌入学习的实体对齐方法，通过其嵌入模块和对齐模块以及其交互的模块进行分类。
Embedding Module
嵌入模型将知识图谱的实体用低纬的向量来表示，根据三元组的类型进行分类，分为Relation Embedding和Attribute Embedding。
- Relation Embedding
1）Triple-based Embedding
这个通过一个能量函数来判断其三元组的可信度，对于关系三元组$(e_1,r_1,e_2)$来说如下面的公式（1），其中TransE使用marginal ranking loss函数去分离正负样例，其他也有选择logistic loss和limit-based loss，而对于负样例一般采取通常的均匀采样和截断采样的方法。
$$
\phi(e_1,r_1,e_2)=||\mathbf{e_1}+\mathbf{r_1}-\mathbf{e_2}0|| \tag {1}
$$
2) Path-based Embedding
基于路径嵌入方法考虑了关系路径之间的相互影响，关系路径就是首尾相连的三元组集合，如样例$(e_1,r_1,e_2),(e_2,r_2,e_3)$这种集合，IPTransE通过推断直连和多跳路径之间有等价性质进行路径建模的。其假设前面实体$e_1$和$e_3$之间有个关系$r_3$，那么其应该和对应的关系路径嵌入表达应该很接近，公式如下：
$$
\mathbf{r}^* = comb(\mathbf{r}_1,\mathbf{r}_2) \tag {2}
$$
这个方法最后同过最小化${||\mathbf{r}^* - \mathbf{r}_3||}$作为损失函数，但是其忽略考虑了实体。其他方法有RSN4EA同过调整Recurrent Neural Networks (RNNs)来对实体和关系序列进行建模。
3）Neighborhood-based Embedding
其通过实体和其邻接点之间以及之间的关系组成的子图进行嵌入学习，GCNs模型非常适合这种结构，而且有研究使用该模型，其模型包含多个图卷层，$\mathbf{A}$表示KG的邻接矩阵，而$\mathbf{H}^{(0)}$表示特征矩阵，每一个对应一个实体，其典型的传播从第i层到（i+1）层的规则如公式（3），其中$\hat{\mathbf{A}} = \mathbf{A} + \mathbf{I}$，其中$\hat{I}$是单位矩阵，$\hat{\mathbf{D}}$是矩阵$\hat{\mathbf{A}}$的对角度矩阵，而矩阵$\mathbf{W}$是学习的权重矩阵（不太理解原理的可以看看如何理解 Graph Convolutional Network（GCN）。
$$
\mathbf{H}^{(i+1)}=\sigma\left(\hat{\mathbf{D}}^{-\frac{1}{2}} \hat{\mathbf{A}} \hat{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{(i)} \mathbf{W}\right) \tag{3}
$$
- Attribute Embedding
属性嵌入学习主要是为了提升实体相似性的评价。
1）Attribute Correlation Embedding
其主要考虑属性之间的相关性，高频率出现在一起对实体进行描述的属性被认为是相关的，例如经度和纬度被认为是相关的，因为其经常一起组合成坐标。JAPE研究了其相关性，基于相似的实体之间应该有相似的相关联的属性，对于属性$a_1,a_2$，其相关的可能性如下式表示，其中属性的嵌入表达可以通过最大化所有的属性对，但是该嵌入方法没有考虑其属性值的影响。
$$
Pr(a_1,a_2)=\operatorname{sigmoid}(\mathbf{a}_1\cdot\mathbf{a}_2) \tag {4}
$$
2）Literal Embedding
AttrE将属性值引入属性嵌入，其使用字符级别的编码，这可以处理没出现在训练集中的值的情况，其$v=(c_1,c_2,\cdots,c_n)$表示n字符，而AttrE使用下面的表达式进行编码，通过对属性值进行嵌入学习，可以将其当做实体和关系元组一样，但是该方法可能在跨语言之间失效。
$$
\mathbf{v} = comb(\mathbf{c}_1,\mathbf{c}_2,\cdots,\mathbf{c}_n) \tag {5}
$$
Alignment Module
对齐模块使用种子实体对作为标签数据进行训练模型，其中两个关键点是距离评估和设计一个对齐推理策略。
- Distance Metrics
Cosine，Euclidean，Manhattan distances是三种常用的测量距离的方法，其中在高纬度的向量空间中有一些向量经常出现在k近邻的邻接点中，这种现象称为hubness现象，后面会详细讨论。
- Alignment Inference Strategies
一种是贪婪搜索，对于一个KG中实体$e_1$，计算其和另一个KG中所有实体之间的相似度，然后去最接近的实体；还有一种有选择的算法就是全局一起计算，然后计算总体的相似度总和，再求整体最小化。
Interaction Mode
- Combination Modes
一共分为四种情况：1）Embedding Space Transformation：其将两个KG嵌入到不同的空间之中，然后通过种子实体对学习一个映射矩阵$M$，使其能够满足$\mathbf{Me}_2 \approx \mathbf{e}_2$。2）Embedding Space Calibration：其将KGs嵌入到统一的空间之中，然后使种子实体对之间的距离$||\mathbf{e}_1-\mathbf{e}_2||$尽可能小。3）Parameter Sharing：直接将对齐的实体对的表示用同一向量表示，相当于将两个知识图谱嵌入到同一空间中了。4）Parameter Swapping：则将对应的三元组中实体替换成其对应的实体，从而构造出一些新的三元组加入训练集。
- Learning Strategies
1）Supervised learning
其使用种子实体对作为便签数据集，对于映射模型则训练映射矩阵，而对于空间校准的则去保证对齐实体有相似的嵌入表达，但是该方法的种子实体对的获取的代价比较高，同时容易出错，特别是对于跨语言的知识图谱。
2）Semi-supervised learning
使用未标签的数据进行训练，一般自我的迭代或者联合训练（实际方法用的也少）。
3）Unsupervised learning
目前好像还没有纯粹使用基于嵌入学习的方法进行无监督的训练方法。
Dataset Generation
如前面所说的，现在的数据集和现实的情况有一定的差距，同时基于嵌入的方法很难在完整的KGs上运行，因为候选空间很大而且没有分区，因此我们对真实的数据集进行了取样，范围为15K和100K。
Iterative Degree-based Sampling
作者通过五个方向来进行分析数据集取样：Source KGs、 Reference Alignment、Dataset Sizes、Languages和Density这五个方面。作者想产生一个和现实数据集大致一致的不同规模的数据集，但是难点在于移除一些实体会改变其相关的邻接点实体的连接性。
本文提出一个基于度的迭代取样算法-Iterative Degree-based Sampling (IDS)，其同时删除在不同KG中的对照实体对，一直到符合要求的规模要求，期间还要保证其度的分布大致相似。下图中的流程介绍了大致的取样过程：
上面的$P(x)$表示目前数据集度为x所占的比例，而$Q(x)$则代表原始数据集中度为x所占的比例，然后每次删除不同度的实体数目通过方程$dsize(x,\mu)=\mu(1+P(x)-Q(x))$来确定，其中$\mu$是一个基本的数目量，其方程就保证比例大了就多删点，小了就少删点。然后作者希望不要删除那些在KG中影响力蛮大的一些实体，就是那些度非常大的实体，为了实现这个作者使用一个方程计算一个实体被删除的可能性，然后进行排序。而其方程$JS$如下面所示，用来评价不同度分布之间的区别：
$$
J S(Q, P)=\frac{1}{2} \sum_{x=1}^{n}\left(Q(x) \log \frac{Q(x)}{M(x)}+P(x) \log \frac{P(x)}{M(x)}\right) \tag {6}
$$
其中$M=\frac{Q+P}{2}$，一个小的$JS$值表示其他们有相似的度分布。而整个流程中最耗时的部分是排序部分的计算，这个部分可以通过使用相似算法推广到大范围的知识图谱。
Dataset Overview
我们选择三个数据集DBpedia、Wikidata、YAGO来产生取样数据集，同时我们考虑跨语言的DBpedia的English-French和English-German。我们使用上面的IDS的算法来取样。
数据集的信息详情如表2，我们产生了两个版本的数据集，$V_1$直接使用IDS算法进行取样，对于$V_2$我们首先随机删除度小于5的实体，使删除后度的平均值变为原先的两倍，然后再用IDS进行取样，后面的数据集密度是前面的两倍，同时其更接近真实的数据集。
通过比较发现，文中产生的数据集更符合实际情况，具体如下图：
Dataset Evaluation
至于算法IDS和数据集的质量的评估，一个好的数据集应该具有良好的连通性、和原数据集有相似的度分布、有足够对齐的实体对。作者采用两个通用的取样算法进行对比评估，下图是三种方法取样后的数据详细情况，还加了一个孤立比例和聚集层度参数两个评价量：
1）Random Alignment Sampling (RAS)
随机取样就是随机去源数据集中取样，然后取出头尾实体都在取样数据集中的关系元组。
2）PageRank-based Sampling (PRS)
基于PageRank算法对一个KG中的实体进行排序，然后在另一个KG中找到对应实体加入数据集中。
Open-source Library
作者使用Python和TensorFlow搭建了一个针对基于嵌入学习的实体对齐的开源库OpenEA。其具体机构和包含模块如下图所示：
1）Loose Coupling
嵌入模块与对齐模块在实施阶段是独立的，其OpenEA提供了预先定义的输入和输出数据结构，这样可以让上图中模块形成一个Pipeline，用户可以自由地组合使用不同的技术去探索新的方法。
2）Functionality and Extensibility
OpenEA工具提供了一些基础的功能作为其组件，包括初始化函数、损失函数和嵌入模块中的负采样方法；交互模块中的整合和学习策略；以及对齐模块中距离评估和对齐推理策略。除此之外，OpenEA还提供一套具有配置功能并调用这些组件的高级选项。这样，使用者可以自由添加新的功能。
3）Off-the-shelf Approaches
为了利用现成的方法，作者将一些列的方法实施在这个开源库上面，具体详见文中介绍。
Experiments and Results
本部分介绍具体的实验类容以及结果之间的对比分析，下面就只展现一些图表分析，每张图标的标题基本解释了其内容。
上图展现了其方法在同一数据集下的表现情况，在密数据集上表现比稀数据集要好一些，一些方法通过上面数据可以显示出一只都表现比较不错。同时作者认为在基于关系的实体对齐方法上看不出来关系嵌入的明显优点，而且使用属性嵌入的方法也对于不方法不明显，但是对于文本的嵌入表示反而对对齐结果影响非常明显。总的来说，属性异构性对捕获属性相关性有很大的影响，而文本嵌入有助于实体对齐。
作者好考虑了半监督训练方法策略的特点，其累计的对齐实体的数量和质量对半监督方法影响很大，如图7。而最后一张图则表明了其不同方法运行时间的大致对比情况。
Exploratory Experiments
Geometric Analysis
除了性能比较，作者想探索一下嵌入空间的几何特性对实体对齐的影响，进而理解方法的局限性。
Similarity Distribution
本文对实体以及其跨图中最近邻接点的相似性分布进行了分析，下面的图9就是展示了各种模型的分布情况，其使用cos来计算其相似度。
那些源实体和其top-1的最近邻接点相似分布越接近的其对齐的效果也好，同时那些相似性在top-5以内的差异越大，其对齐的效果也好，也就是说，如果相似性分布在top-1之内相近，而在之外相似度差异变大更利于实体对齐任务。即对于实体对齐而言，理想的相似度分布是保持较高的top-1相似度，和较大的相似度方差。
Hubness and Isolation
Hubness是在高纬度向量空间中经常出现的现象，一些结点经常出现在top-1的位置上，再就是有一些节点不会出现在任何的集合中，即一些孤立的点。上图10中就表现了一些结点出现次数为0，其所占的比例还不小，这些节点对于实体对齐来说是非常大干扰，同时结合试验结果来看，其这两个部分所占的比例越小，其实体对齐的准确性越高，所以这两个比例成分可以用来预测数据集的最终的实体对齐的效果。
为了解决这个问题，作者想出了Cross-domain Similarity local Scaling (CSLS)，它根据源和目标嵌入实体的相邻嵌入密度，对嵌入实体的相似性进行规格化，公式如下：
$$
{CSLS(\mathbf{x}s,\mathbf{x}_t)=2cos(\mathbf{x}_s,\mathbf{x}_t)-\psi{t}(\mathbf{x}s)-\psi{s}(\mathbf{x}_t)} \tag {7}
$$
其中${\psi_{t}(\mathbf{x}s)}$表示源实体${\mathbf{x}_s}$和其目标KG中top-k近邻的平均相似度，对于${\psi{x}(\mathbf{x}_t)}$含义相反，上述公式减少了Hub实体与其他实体的相似度，就是降低其被选择的概率，同时这个也可以提升孤立节点被选择到可能性，从而缓解上述的两种现象。上面的图显示了其使用该方法后效果提升情况。作者经过分析，存在的方法一般关注于设计更有效的嵌入和交互模块，但是一些对齐模块的方法也可以提升其实体对齐的结果。
Unexplored KG Embedding Models
如上面展示的方法，许多存在的方法使用TransE或者GCNs来进行KG嵌入学习，因为其方法具有鲁棒性和普遍性。但是还有很多方法没被探索应用到实体对齐。作者评估了三种平移模型，两中深度模型，和三种语义模型进行试验，结果如下：
经过分析作者认为并非所有的KG嵌入模型都适合实体对齐任务，而且非欧几里得嵌入模型值得进一步研究探索。
Comparison to Conventional Approaches
作者进一步和传统的LogMap（Semantic Web community）和PARIS（Database community）方法进行了对比实验：
经过分析，传统的方法对含有属性的情况表现比较好，而基于嵌入学习模型能够适应大多数包含关系信息或者属性信息的情况（具体分析可以见原文）。
Summary and Future Directions
Summary：经过上述的实验，其中RDGCN、BootEA **和MultiKE**三种模型表现一直很不错，这个表明联合文本信息和精心设计的迭代过程有助于提升对齐的性能；嵌入模型用来进行实体链接并非所有的模型都合适；同时对于实体对齐的推理策略目前研究还不多，值得后续进一步研究；同时作者发现基于嵌入模型和传统的模型之间是相互互补的；下图整理一些模型需要的必要信息。
Future Directions：作者基于上述的研究，提出了一些后续值得研究的方向：1）无监督的实体对齐；2）长尾类型的实体对齐；3）大规模的实体对齐；4）非欧几里德空间的实体对齐