Yuting Wu, Xiao Liu, Yansong Feng, Zheng Wang and Dongyan Zhao, “Neighborhood Matching Network for Entity Alignment”, ACL 2020
1 简介
本文的领域是实体对齐。以往的实体对齐算法,比如要从图 B 中匹配图 A 中的实体 a,就要从 B 中找到和 a 有相似邻居结构的实体 b。因为这俩实体的邻居结构差不多,所以这俩的 embedding 也就差不多,这俩也就很可能成为匹配的实体。
而作者发现,在实体对齐中,会存在“结构异质性(structural heterogeneity)”的情况,即来自两个不同的知识图谱的实体,这俩各自的邻居结构可能是不同的。比如实体不同的邻居个数、周围不同的拓补结构等等。作者把结构异质性导致的问题分成三方面:
- 邻居数量可能不同:在数据集里每个实体的邻居个数变得不平均时,之前方法的性能会大幅下降。
- 拓扑结构可能不同:【#TODO1 邻居不就是距离为一的点吗?还有什么结构可不同的?】
- 即使邻居数量差不多,比如我们都选最近的 5 个,但是这样就行了吗?我们选出来的这 5 个邻居可能并不能很好地表示中心的实体。(可能在语义上不一样的实体,也会共享这些邻居)所以需要一个方法,来选“好邻居”。
对于问题 1,作者就挑选固定数量个(见 3.3);对于问题 2,作者先用 GCN 做 embedding(见 3.2);对于问题 3,作者挑选跟中心实体语义接近的,作为关键邻居(见 3.3)。作者还设计一个邻居匹配的算法,同时使用中心实体和关键邻居的信息,在另外一个图谱中做匹配(见 3.4)。最终在 DBP15K 和 DWY100K 取得 SOTA。
2 相关工作
这篇文章这部分写的很不好,就直接罗列论文,连稍微介绍几句都没有(或者是因为我太菜了)。
2.1 基于嵌入的实体对齐
基于嵌入就是先得到实体的特征表示。有人用图的结构信息【TODO1】,有人用 GCN embed 图结构信息、有人用外部信息改进特征表示。这些嵌入的方法都没考虑结构异质性。MuGNN 和 AliNet 考虑了结构异质性,然而,前者需要对齐的实体和关系作为监督训练样本,标注太难了;后者最后拼接的时候,所有邻居都用,并不太合理,增加了噪声。俺们 NMN 选关键邻居,比他们都好。
2.2 图神经网络
我现在就知道,这玩意是把传统的神经网络,在结构上从二三维搞到高维,具体还没了解。正好这里给出三篇论文,列入【#TODO2】
2.3 图的匹配
就是本文的 3.4 部分,是从 Graph Matching Network (GMN) (Li et al., 2019b) 抄的。
3 算法
前面废话说的有点多,终于进入正题了。先来描述一下问题:
首先,把知识图谱表示成 $G=(E,R,T)$ 的集合,其中 $E,R,T$ 分别是 实体、关系、三元组。实体对齐的目的,就是在两个知识图谱 $KG1$ 和 $KG2$ 之中,找到相等的实体对。
3.1 总体流程

如图分四步,① 用 GCN 做 embedding,让特征表示里包含图的结构信息;② 选好邻居,中心实体和它的好邻居组成一个子图;③ 用两个图谱之间的子图做匹配,得到每个邻居关于“能否匹配对方”的一个特征表示;④ neighborhood aggregation【#TODO3】,得到最后的特征表示。
3.2 结构嵌入
NMN 使用预训练的词向量,作为 GCN 的输入。GCN 的每层都输入一些结点的特征,按下面的式子更新结点的特征表示:
$$h_i^{(l)} = RELU(\sum_{j\in N_i\cup \{i\}}\frac{1}{\epsilon_i}W^{(l)}h_j^{(l-1)})$$
其中 $\{h_1^{(l)},h_2^{(l)},…,h_n^{(l)}|h_i^{(l)}\in \mathcal{R}^{d^{(l)}}\}$ 是 GCN 第 $l$ 层中实体的特征表示,$\epsilon_i$ 归一化常数,$N_i$ 是结点 $i$ 邻居的集合,$W^{(l)} \in \mathcal{R}^{d^{(l)}\times d^{(l-1)}}$ 是待训练的参数。
在训练过程中,还使用【#TODO4】的方法优化了一下,减少误差积累。(这篇文章真是一个大杂烩)
3.3 邻居采样
什么是邻居采样?后面要进行实体匹配,就是计算两个图谱之间的实体的相似度。怎么计算相似度?这里不仅要用到实体自己的信息,还要用到它的邻居的信息。
上面说过,不能只要距离是 1,就当做邻居,这样会引入很多噪声。因此要从邻居里挑“好邻居”,这就是邻居采样的过程。那什么是好邻居呢?作者认为,一对邻居实体的共现频率越高,那么这个邻居对中心实体的特征表示,在语义上就更有信息量;信息量越多,就能更好地表示这个中心的实体,就是好邻居。那什么样的两个实体共现频率高呢?
我们知道,能匹配出来的一对实体,他俩会有差不多的邻居。那么在中心实体周围,语义和中心实体更接近的,就更是“好邻居”。(这句话的原文是 “Since the contexts of two equivalent entities in real-world corpora are usually similar, the stronger a neighbor is contextually related to the target entity, the more alignment clues the neighbor is likely to offer.” 感觉没把道理讲清楚。我的理解是,从现实角度考虑,好邻居当然不一定要和中心实体的语义很接近,但是,如果邻居的语义和中心实体相去甚远,那它一定不是好邻居。因此选择语义接近的,可以排除坏邻居。)
于是可以计算中心实体 $e_i$ 的邻居 $e_{i-j}$ 是好邻居的概率:
$$ \begin{aligned} p(h_{i-j}|h_{i}) &= softmax(h_iW_sh_{i-j}^T)\\ &= \frac{exp(h_iW_sh_{i-j}^T)}{\sum_{k\in N_i}(h_iW_sh_{i-j}^T)} \end{aligned} $$
其中 $N_i$ 是 $e_i$ 邻居的集合。
至于选最好的几个邻居呢?实验调参见。
3.4 邻居匹配
分两步,先从对方的知识图谱中挑选出 $k$ 个跟我这边要匹配实体相似度最大的实体,作为备选集合;然后在备选集合里,挨个计算“子图的相似度”,得到“子图匹配的向量”(原文 matching vector)$m_p$。
3.4.1 选备胎
即对于待匹配的实体 $e_i\in E_1$,挑选出备胎集合 $\mathcal{C}_i=\{c_{i_1},c_{i_2},…,c_{i_k}|c_{i_k}\in E_2\}$。方法也很朴素(因为加这一步就是为了先排除点,减少后一步的复杂度),就是计算词向量的相似度,过一层 softmax 挑最大的。$E_2$ 中的实体 $e_j$ 是 $e_i$ 备胎的概率为:
$$p(h_j|h_i) = \frac{exp(\|h_i-h_j\|_{L_1})}{\sum_{k\in E_2}exp(\|h_i-h_k\|_{L_1})}$$
3.4.2 子图匹配
令 $(e_i,c_{i_k})$ 为一个实体对,其中 $e_i\in E_i$ 是中心实体,$c_{i_k}\in E_2$ 是备胎之一。$p$ 是 $e_i$ 的一个邻居,$q$ 是 $c_{i_k}$ 的一个邻居。那么 $p$ 的“子图匹配向量” $m_p$ 就是:
$$a_{pq} = \frac{exp(h_p\cdot h_q)}{\sum_{q’\in N_{i_k}^s }exp(h_p\cdot h_{q’})}$$
$$m_p = \sum_{q\in N_{i_k}^s}a_{pq}(h_p-h_q)$$
其中 $a_{pq}$ 是 attention 机制,相当于挑选出和 $p$ 最匹配的 $q$,$m_p$ 是 $p$ 到 $c_{i_k}$ 整个子图的匹配向量,衡量 $p$ 和 $q$ 的“距离”(这时 $q$ 已经是 attention 挑出来的,在 $E_2$ 中和 $p$ 最相似的实体了)。然后再把 $m_p$ 和 GCN 得到的 $p$ 的表示 $h_p$ 拼接,得到 $\hat{h}_p$,也就是 $p$ 最终的特征表示。
为什么要设计这样一个 $m_p$ 拼在后面呢?我认为:
- 到你那里,匹配我最近的邻居——用 attention 是很朴素的想法;
- 把匹配相似度拼在我邻居的特征表示后面,这样就在我的知识图谱中引入了一点点你的信息,如果本身就很匹配,那么可以加强这个匹配的效果?
- 我其实还是不太懂,这明明只是一个从 $e_i$ 到 $c_{i_k}$ 这两个子图之间的匹配过程,凭啥生成的东西就能加入 $h_p$ 这样一个全局的特征表示呢?$c_{i_k}$ 又是怎么选的呢?刚才不是选出一堆备胎吗?现在怎么只有一个了?这部分代码我也看不懂,晕。【#TODO5】
3.5 得到最终表示
这步在文章中叫“Neighborhood Aggregation”,上面得到了实体 $e_i$ 的一个邻居 $p$ 的特征表示 $\hat{h}_p$,这一步就是要用 $e_i$ 的所有好邻居的特征表示,得到 $e_i$ 的新的特征表示。令 $e_i$ 的邻居表示为:
$$g_i = (\sum_{p\in N_i^s}\sigma(\hat{h}_pW_{gate})\cdot \hat{h}_p)W_N$$
这个原理我也不懂,作者说他是抄的【#TODO3】这篇文章,我回来再看吧。
最后还是,把 $g_i$ 和原来 GCN 得到的 $h_i$ 拼一起,得到 $e_i$ 的新的特征表示 $\hat{h}_i^{match}$
3.6 训练过程
分两步
3.6.1 预训练
一开始先通过 GCN 得到了 embedding,但是这里得到的特征表示只包含图谱本身的内容、结构信息。这里预训练,是拿能对齐的实体作为标签,有监督训练,微调一下特征表示,使“要对齐的”距离尽量小,“不对齐的”距离尽量大。目标函数为:
$$\tilde{L} = \sum_{(i,j\in \mathcal{L})}\sum_{(i’,j’)\in\mathcal{L’}} \max \{0,\tilde{d}(i,j) – \tilde{d}(i’,j’) + \gamma\}$$
其中,距离 $\tilde{d}$ 由 $h_i$ 和 $h_j$ 之差的 L1 范数表示,$\mathcal{L}$ 是要对齐的正样本集合,$\mathcal{L’}$ 是负样本集合。负样本是由【#TODO6】的算法生成的。
那么这个式子的意思就是,尽量让正样本距离更近,负样本距离更远。不过为啥这样设计?这还是我第一次见,可能是这种“正负样本”优化问题的套路吧,还得再多看看别人的文章【#TODO7 – 已解决,来自 TransE】。
3.6.2 训练
全局的损失函数跟上面差不多:
$$L = \sum_{(i,j\in \mathcal{L})}\sum_{(i’,j’)\in\mathcal{C}} \max \{0,d(i,j) – d(i’,j’) + \gamma\}$$
其中,距离 $d$ 由 $\hat{h}_i$ 和 $\hat{h}_j$ 之差的 L1 范数表示,$\mathcal{C}$ 是负样本集合。此处的负样本并不是“不能对齐”的样本,而是 3.4.1 步骤中选出来的备胎。这样优化的过程,就是在备胎中选择最好的,贴近;其它的,远离(不确定我想的对不对)。负样本集合的表示为:
$$\mathcal{C} = {(r’,t’)|(r’=r \wedge t’ \in \mathcal{C}_r )\vee (t’=t \wedge r’ \in \mathcal{C}_t )}$$
我看不懂。。。【#TODO8】
另外,3.3 中的 $W_N$ 还没能迭代优化,于是就每全局优化 50 epoch,再优化一下 $W_N$。优化 $W_N$ 的目标函数是:
$$L_w = \sum_{(r,t)\in \mathcal{L}}|g_r^{w} – g_t^{w}|_{L_1}$$
就是让应该对齐的实体,距离更小。
4 实验+分析
4.1 数据集
- DBP15K:要匹配的俩知识图谱语言不一样。作者是用 Google 翻译成不同语言的。
- DWY100K:要匹配的俩图谱,知识库不一样。
- S-DBP15K:稀疏的 DBP15K(sparse alignment clues),就是随机移除一些三元组,让“结构异质性”更明显。
4.2 实验结果
总体上
- 以上所有数据集,SOTA。
- MuGNN 和 AliNet 次之,说明处理结构异质性很有用。
- 使用实体名信息的方法更次之,说明实体的内容信息也有用。
- 只用图谱结构信息的方法,最次。
在每个步骤上
- 3.4.1 是有效的,比别人的“邻居全选”或者“只选最近的”都好。
- 若分别去掉 3.4 或者 3.5,性能都下降,说明这两步都有用。
- 3.4.2 画出 attention 权重的图,的确有用,能匹配到相等的邻居。
- 选几个好邻居呢?在不同数据集不一样。如果这个数据集质量好,那就多选点;质量差,就少选点(否则带来噪声)。
在结构异质性问题上
- 在 S-DBP15K 上比其他算法的 gap 更大,说明咱们 NMN 更适应 sparse alignment clues。
- 3.5 这一步可以在 sparse alignment clues 时,增强这些 clue。
- 3.4 这一步现在太简单了,在 S-DBP15K 上没啥用,还需要改善。
5 总结
- 师姐真是很好地掌握了排除法,包括 3.3 和 3.4.1 的排除。不是只有义正言辞地正面进军才能致胜,外线作战,后路包围也可!
- 这文章真是大杂烩,是我读过的工作量最多的了;
- 这文章真是大杂烩,作为我看的第一篇实体对齐文章,要补的好多 Orz;
6 TODO
- GCN + 图谱相关论文:GCN-Align、GMNN、RDGCN、AVR-GCN、HGCN-JE
- GNN:Graph Convolutional Network (GCN) (Kipf and Welling, 2017), the Relational Graph Convolutional Network (Schlichtkrull et al., 2018), the Graph Attention Network (Velickovic et al., 2018).
- Yujia Li, Richard Zemel, Marc Brockschmidt, and Daniel Tarlow. 2016. Gated graph sequence neural networks. In Proceedings of ICLR’16.
- Rupesh Kumar Srivastava, Klaus Greff, and Ju ̈rgen Schmidhuber. 2015. Highway networks. arXiv preprint arXiv:1505.00387.
- 见文中描述
- Bhushan Kotnis and Vivi Nastase. 2017. Analysis of the impact of negative sampling on link prediction in knowledge graphs. arXiv preprint arXiv:1708.06816.
- 为什么这样设计 Loss? – 已解决,来自 TransE
- 负样本这是啥意思?
[mathjax]