论文笔记 – Neighborhood Matching Network for Entity Alignment

2020-08-04

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）”的情况，即来自两个不同的知识图谱的实体，这俩各自的邻居结构可能是不同的。比如实体不同的邻居个数、周围不同的拓补结构等等。作者把结构异质性导致的问题分成三方面：

  1. 邻居数量可能不同：在数据集里每个实体的邻居个数变得不平均时，之前方法的性能会大幅下降。
  2. 拓扑结构可能不同：【#TODO1 邻居不就是距离为一的点吗？还有什么结构可不同的？】
  3. 即使邻居数量差不多，比如我们都选最近的 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$ 拼在后面呢？我认为：

  1. 到你那里，匹配我最近的邻居——用 attention 是很朴素的想法；
  2. 把匹配相似度拼在我邻居的特征表示后面，这样就在我的知识图谱中引入了一点点你的信息，如果本身就很匹配，那么可以加强这个匹配的效果？
  3. 我其实还是不太懂，这明明只是一个从 $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 数据集

  1. DBP15K：要匹配的俩知识图谱语言不一样。作者是用 Google 翻译成不同语言的。
  2. DWY100K：要匹配的俩图谱，知识库不一样。
  3. S-DBP15K：稀疏的 DBP15K（sparse alignment clues），就是随机移除一些三元组，让“结构异质性”更明显。

4.2 实验结果

总体上

  1. 以上所有数据集，SOTA。
  2. MuGNN 和 AliNet 次之，说明处理结构异质性很有用。
  3. 使用实体名信息的方法更次之，说明实体的内容信息也有用。
  4. 只用图谱结构信息的方法，最次。

在每个步骤上

  1. 3.4.1 是有效的，比别人的“邻居全选”或者“只选最近的”都好。
  2. 若分别去掉 3.4 或者 3.5，性能都下降，说明这两步都有用。
  3. 3.4.2 画出 attention 权重的图，的确有用，能匹配到相等的邻居。
  4. 选几个好邻居呢？在不同数据集不一样。如果这个数据集质量好，那就多选点；质量差，就少选点（否则带来噪声）。

在结构异质性问题上

  1. 在 S-DBP15K 上比其他算法的 gap 更大，说明咱们 NMN 更适应 sparse alignment clues。
  2. 3.5 这一步可以在 sparse alignment clues 时，增强这些 clue。
  3. 3.4 这一步现在太简单了，在 S-DBP15K 上没啥用，还需要改善。

5 总结

  1. 师姐真是很好地掌握了排除法，包括 3.3 和 3.4.1 的排除。不是只有义正言辞地正面进军才能致胜，外线作战，后路包围也可！
  2. 这文章真是大杂烩，是我读过的工作量最多的了；
  3. 这文章真是大杂烩，作为我看的第一篇实体对齐文章，要补的好多 Orz；

6 TODO

  1. GCN + 图谱相关论文：GCN-Align、GMNN、RDGCN、AVR-GCN、HGCN-JE
  2. 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).
  3. Yujia Li, Richard Zemel, Marc Brockschmidt, and Daniel Tarlow. 2016. Gated graph sequence neural networks. In Proceedings of ICLR’16.
  4. Rupesh Kumar Srivastava, Klaus Greff, and Ju ̈rgen Schmidhuber. 2015. Highway networks. arXiv preprint arXiv:1505.00387.
  5. 见文中描述
  6. Bhushan Kotnis and Vivi Nastase. 2017. Analysis of the impact of negative sampling on link prediction in knowledge graphs. arXiv preprint arXiv:1708.06816.
  7. 为什么这样设计 Loss？ – 已解决，来自 TransE
  8. 负样本这是啥意思？

[mathjax]

发表评论