论文笔记007-Neighborhood Matching Network for Entity Alignment

1. 简介

题目：《Neighborhood Matching Network for Entity Alignment》

来源：ACL-2020

链接：论文链接

代码：Code和Dataset

关键字：Entity Alignment

2. 研究背景

  从原先的大量依赖人工的参与实体对齐任务，到Embedding-Based的实体对齐方法的出现，大大缩减了人为的参与度，但是依旧需要一定量的训练种子对，然后提出了基于GCN的相关方法，这些方法有一个假设前提-相似实体对的周围邻近结构也会很相似。但是实际情况不是这样的。如下图：

  从上图中可以看到，对于有些对齐的实体，其周围的邻接点数目相差是很大的，而且就算不考虑数量的差别（图中第二组），其邻接点中相似的数量也很少，很多节点都是不相似，同时作者通过实验发现，随着邻接点的数目增加，其Embedding-Based方法的准确率会大大下降，同时邻接点的数目增多，同时其评价邻接点的相似度的难度也很大，其GCN方法的计算量的代价也会大大增加。作者由此分析提出了相应的改进的NMN模型。

3.Related Work

  作者在本段落介绍了其模型四个组成部分的相关研究状况。

3.1 Embedding-based entity alignment

  早期的Embedding-Based方法TransE-2013，通过对KG的结构进行编码来实现对齐，其变形有MTransE-2017、JAPE-2017、IPTransE-2017、BootEA-2018、NAEA-2019、OTEA-2019。最近提出的模型用GCN去对KG建模，如GCN-Align-2018、GMNN-2019、RDGCN-2019、AVR-GCN-2019、HGCN-JE-2019。除了使用结构信息，还有使用其他信息的方法，如KDCoE-2018、AttrE-2019、MultiKE-2019、HMAN-2019这些方法使用其他的信息去改善实体的表示学习。

  然而上面的方法都忽视了其邻接点的异构性。MuGNN-2019和AliNet-2020最新的两个去解决这个问题的模型。但是其两个模型依旧有些缺点，前者需要大量预先训练的实体和关系数据，这个很代价很高。后者模型只考虑的一阶邻接点同等的重要性，然后并非所有的一阶邻接点都重要，作者考虑到上述的缺点，自己的模型NMN只会提取一些有用的邻接点，同时只需要一些预先训练的数据。

3.2 Graph neural networks

  GNNs模型最近被很多NLP的研究使用，如语义标签和机器翻译等。GNNs的结点表达通过不断的迭代聚集周围邻接点的表达，目前有很多其变种模型，如Graph Convolutional Network (GCN)-2017、Relational Graph Convolutional Network-2018、Graph Attention Network-2018等，考虑到其模型对图结构的优越性，作者也是使用图模型去建模结构信息。

3.3 Graph matching

  图之间的匹配测量一般通过精准的匹配或者通过结构信息计算编辑距离， 近年来一个模型Graph MatchingNetwork (GMN) (Li et al., 2019b)，其是通过基于注意力机在图对上进行推理匹配的方法，作者采纳其类似的方法去捕获邻接点的差异点。

3.4 Graph sampling

  这个图取样一般会选取原图中一部分结点或者边，一些流行的方法有vertex-、 edge-和raversal-based sampling这三类，作者采用的是选取结点的方法，去选取一些有用的邻接点。

4. Approach

  作者将知识图谱表示为 G = ( E , R , T ) G=(E,R,T) G=(E,R,T)，分别表示实体、关系、三元组。

4.1 Overview of NMN

  作者的模型分为4部分：1）Structure Embedding， 2）Neighborhood Sampling，3）Neighborhood Matching，4）Neighborhood Aggregation for Generating Embeddings，其将两个图一起输入模型，同时进行嵌入学习，最后通过学习到的表示计算实体之间距离判断相似性，如下图：

4.2 KG Structure Embedding

  为了学习实体的表示，作者这里使用多层GCN去聚集高纬的邻接点结构信息，NMN使用了预先已经训练好的词向量初始化图，这个策略在（Xu et al., 2019； Wu et al., 2019a）研究中被证实了是很有效去学习实体名的编码方式。作者将两个图一起作为GCN的输入，每层更新结点表示的方法如下：
h i ( l ) = ReLU ⁡ ( ∑ j ∈ N i ∪ { i } 1 ϵ i W ( l ) h j ( l − 1 ) ) (1) \boldsymbol{h}_{i}^{(l)}=\operatorname{ReLU}\left(\sum_{j \in N_{i} \cup\{i\}} \frac{1}{\epsilon_{i}} \mathbf{W}^{(l)} \boldsymbol{h}_{j}^{(l-1)}\right) \tag {1} hi(l)​=ReLU⎝⎛​j∈Ni​∪{i}∑​ϵi​1​W(l)hj(l−1)​⎠⎞​(1)
  其中 { h 1 ( l ) , h 2 ( l ) , … , h n ( l ) ∣ h i ( l ) ∈ R d ( l ) } \left\{\boldsymbol{h}_{1}^{(l)}, \boldsymbol{h}_{2}^{(l)}, \ldots, \boldsymbol{h}_{n}^{(l)} \mid \boldsymbol{h}_{i}^{(l)} \in \mathbb{R}^{d^{(l)}}\right\} {h1(l)​,h2(l)​,…,hn(l)​∣hi(l)​∈Rd(l)}是第 l l l层GCN的输出结点特征，而其中的 ϵ i \epsilon_{i} ϵi​是归一化常数， N i N_{i} Ni​是结点 i i i的邻接点集合，而 W ( l ) ∈ R d ( l ) × ( l − 1 ) \mathbf{W}^{(l)}\in \mathbb{R}^{d^{(l)\times (l-1)} } W(l)∈Rd(l)×(l−1)是第 i i i层的参数。为了控制累积误差的影响，作者这里引入了门控网络。

4.3 Neighborhood Sampling

  实体的一阶邻接点对于其对齐的判断非常重要，但是不是所有的邻接点都有用，作者模型中采用了一种降采样的方式，只选取最有用的邻接点。作者这里认为：一个邻接点越出现在实体的面前频率越高，其对中心实体的重要性就越高。显示中联系越紧密的经常一起出现在上下文中。

  对于给定实体 i i i，其邻接结点 e i _ j e_{i\_j} ei_j​的取样概率如下：
p ( h i − j ∣ h i ) = softmax ⁡ ( h i W s h i − j T ) = exp ⁡ ( h i W s h i − j T ) ∑ k ∈ N i exp ⁡ ( h i W s h i − k T ) (2) \begin{aligned} p\left(\boldsymbol{h}_{i_{-} j} \mid \boldsymbol{h}_{i}\right) &=\operatorname{softmax}\left(\boldsymbol{h}_{i} \mathbf{W}_{s} \boldsymbol{h}_{i_{-} j}^{T}\right) \\ &=\frac{\exp \left(\boldsymbol{h}_{i} \mathbf{W}_{s} \boldsymbol{h}_{i_{-} j}^{T}\right)}{\sum_{k \in N_{i}} \exp \left(\boldsymbol{h}_{i} \mathbf{W}_{s} \boldsymbol{h}_{i_{-} k}^{T}\right)} \end{aligned} \tag {2} p(hi−​j​∣hi​)​=softmax(hi​Ws​hi−​jT​)=∑k∈Ni​​exp(hi​Ws​hi−​kT​)exp(hi​Ws​hi−​jT​)​​(2)
  其中 N i N_{i} Ni​是一阶邻结点的指示集合， h i h_{i} hi​和 h i _ j h_{i\_j} hi_j​是学习到的实体表达，而 W s \mathbf{W}_{s} Ws​是共享的参数矩阵。

4.4 Neighborhood Matching

  作者通过上面的取样以后，后续的操作只会在对应的子图上面进行。作者认为相似实体的邻接点也会尽可能相似，作者通过这个思路来判断邻接点的相似性。

Candidate selection

  作者考虑到，要是针对实体 i i i的子图和另一个KG中的所有实体子图进行比较，然后再去选择最相似的子图，这样会非常耗费时间，所以作者先选择一些可能相似的实体候选集合出来，然后就只和这些集合里面的元素进行比较，这样会大大降低计算量。而对于被选择的后续实体选取规格如下：
p ( h j ∣ h i ) = exp ⁡ ( ∥ h i − h j ∥ L 1 ) ∑ k ∈ E 2 exp ⁡ ( ∥ h i − h k ∥ L 1 ) (3) p\left(\boldsymbol{h}_{j} \mid \boldsymbol{h}_{i}\right)=\frac{\exp \left(\left\|\boldsymbol{h}_{i}-\boldsymbol{h}_{j}\right\|_{L_{1}}\right)}{\sum_{k \in E_{2}} \exp \left(\left\|\boldsymbol{h}_{i}-\boldsymbol{h}_{k}\right\|_{L_{1}}\right)} \tag {3} p(hj​∣hi​)=∑k∈E2​​exp(∥hi​−hk​∥L1​​)exp(∥hi​−hj​∥L1​​)​(3)
Cross-graph neighborhood matching

  作者收到图匹配研究的启发，其将所有的子图作为输入，为每一个邻接点计算其对应的匹配向量， ( e i , c i k ) (e_i,c_{ik}) (ei​,cik​)是要评价的实体对，其分别属于 E 1 E_{1} E1​和 E 2 E_{2} E2​，而且 c i k c_{ik} cik​是实体 e i e_{i} ei​的候选集中的， p p p和 q q q分别是实体 e i e_{i} ei​和 e i k e_{ik} eik​的邻接点，那么对于实体 q q q的跨图的匹配向量是：
a p q = exp ⁡ ( h p ⋅ h q ) ∑ q ′ ∈ N i k s exp ⁡ ( h p ⋅ h q ′ ) (4) a_{p q}= \frac{\exp \left(\boldsymbol{h}_{p} \cdot \boldsymbol{h}_{q}\right)}{\sum_{q^{\prime} \in N_{i_{k}}^{s}} \exp \left(\boldsymbol{h}_{p} \cdot \boldsymbol{h}_{q^{\prime}}\right)} \tag {4} apq​=∑q′∈Nik​s​​exp(hp​⋅hq′​)exp(hp​⋅hq​)​(4)

m p = ∑ q ∈ N i k s a p q ( h p − h q ) (5) \boldsymbol{m}_{p} =\sum_{q \in N_{i_{k}}^{s}} a_{p q}\left(\boldsymbol{h}_{p}-\boldsymbol{h}_{q}\right) \tag {5} mp​=q∈Nik​s​∑​apq​(hp​−hq​)(5)

  其中 q p q q_{pq} qpq​是一个注意力权重， m p m_{p} mp​是一个匹配向量，其描绘了其他对应子图中最近邻接点和 h p h_{p} hp​之间差别。然后作者将其输出和原先的结点表达联合：
h ^ p = [ h p ∥ β ∗ m p ] (6) \hat{h}_{p}=\left[h_{p} \| \beta * m_{p}\right] \tag {6} h^p​=[hp​∥β∗mp​](6)
  匹配向量对于相似的两个邻接点，其值接近于 0 0 0向量，其表达就非常而接近，而对于不相似的结点，其不对称会在传播过程中不断增大，最后结果证明该匹配机制很有效。

4.5 Neighborhood Aggregation

  这个模块就是整合其邻接点的连接信息，即结构嵌入表示，同时将上一步匹配网络学习到的匹配信息结合在一起，对于其取样的的邻接点 { h ^ p } \{\hat{h}_{p}\} {h^p​}，对于实体 i i i来说其匹配网络学习到的邻接点表示为 g i g_{i} gi​，然后将其和结构嵌入表示联结起来：
g i = ( ∑ p ∈ N i s σ ( h ^ p W g a t e ) ⋅ h ^ p ) W N (7) \boldsymbol{g}_{i}=\left(\sum_{p \in N_{i}^{s}} \sigma\left(\hat{\boldsymbol{h}}_{p} \mathbf{W}_{g a t e}\right) \cdot \hat{\boldsymbol{h}}_{p}\right) \mathbf{W}_{N} \tag {7} gi​=⎝⎛​p∈Nis​∑​σ(h^p​Wgate​)⋅h^p​⎠⎞​WN​(7)
h i match = [ g i ∥ h i ] (8) \boldsymbol{h}_{i}^{\text {match}}=\left[\boldsymbol{g}_{i} \| \boldsymbol{h}_{i}\right] \tag {8} himatch​=[gi​∥hi​](8)

5. Entity Alignment and Training

Pre-training

  作者首先预先训练基于GCN的嵌入模型去提供可信的实体表达，里面通过测量两个实体的距离来判断是否应该对齐：
d ~ ( e 1 , e 2 ) = ∥ h e 1 − h e 2 ∥ L 1 (9) \tilde{d}\left(e_{1}, e_{2}\right)=\left\|\boldsymbol{h}_{e_{1}}-\boldsymbol{h}_{e_{2}}\right\|_{L_{1}} \tag {9} d~(e1​,e2​)=∥he1​​−he2​​∥L1​​(9)
  其训练的目标函数为，其中 γ \gamma γ > 0，而 L \mathbb{L} L和 L ′ \mathbb{L}^{\prime} L′分别代表种子实体对和负样本（在最近的结点中替换）：
L ~ = ∑ ( i , j ) ∈ L ( i ′ , j ′ ) ∈ L ′ max ⁡ { 0 , d ~ ( i , j ) − d ~ ( i ′ , j ′ ) + γ } (10) \tilde{L}=\sum_{(i, j) \in \mathbb{L}\left(i^{\prime}, j^{\prime}\right) \in \mathbb{L}^{\prime}} \max \left\{0, \tilde{d}(i, j)-\tilde{d}\left(i^{\prime}, j^{\prime}\right)+\gamma\right\} \tag {10} L~=(i,j)∈L(i′,j′)∈L′∑​max{0,d~(i,j)−d~(i′,j′)+γ}(10)
Overall training objective

  如果实体对齐预训练完成，预训练阶段已经收敛到稳定状态，其会给后续的部分提供充足的信息。因此后续的损失函数会修改为如下：
L = ∑ ( r , t ) ∈ L ∑ ( r ′ , t ′ ) ∈ C max ⁡ { 0 , d ( r , t ) − d ( r ′ , t ′ ) + γ } (11) L=\sum_{(r, t) \in \mathbb{L}} \sum_{\left(r^{\prime}, t^{\prime}\right) \in \mathbb{C}}\max \left\{0, d(r, t)-d\left(r^{\prime}, t^{\prime}\right)+\gamma\right\} \tag {11} L=(r,t)∈L∑​(r′,t′)∈C∑​max{0,d(r,t)−d(r′,t′)+γ}(11)

d ( r , t ) = ∥ h r match − h t match ∥ L 1 (12) d(r, t)=\left\|\boldsymbol{h}_{r}^{\text {match}}-\boldsymbol{h}_{t}^{\text {match}}\right\|_{L_{1}} \tag {12} d(r,t)=∥∥∥​hrmatch​−htmatch​∥∥∥​L1​​(12)

  其中负样例集合 C = \mathbb{C}= C= { ( r ′ , t ′ ) ∣ ( r ′ = r ∧ t ′ ∈ C r ) ∨ ( t ′ = t ∧ r ′ ∈ C t ) } \left\{\left(r^{\prime}, t^{\prime}\right) \mid\left(r^{\prime}=r \wedge t^{\prime} \in \mathcal{C}_{r}\right) \vee\left(t^{\prime}=t \wedge r^{\prime} \in \mathcal{C}_{t}\right)\right\} {(r′,t′)∣(r′=r∧t′∈Cr​)∨(t′=t∧r′∈Ct​)} 是由候选集合 C r \mathcal{C}_{r} Cr​ 和 C t \mathcal{C}_{t} Ct​组成（4.4中选择的）。注意到，我们的取样过程是不可微分的，所以其阻断了参数矩阵 W s \mathbf{W}_{s} Ws​（公式2）的训练，为了训练其值，我们不直接取样，我们整合所有的邻接点的信息如下：
g i w = ( ∑ p ∈ N i α i p ⋅ σ ( h ^ p W g a t e ) ⋅ h ^ p ) W N (13) \boldsymbol{g}_{i}^{w}=\left(\sum_{p \in N_{i}} \alpha_{i p} \cdot \sigma\left(\hat{\boldsymbol{h}}_{p} \mathbf{W}_{g a t e}\right) \cdot \hat{\boldsymbol{h}}_{p}\right) \mathbf{W}_{N} \tag {13} giw​=⎝⎛​p∈Ni​∑​αip​⋅σ(h^p​Wgate​)⋅h^p​⎠⎞​WN​(13)
  其中 α i p \alpha_{i p} αip​是一个聚合的权重，即式子2中的 p ( h j ∣ h i ) p\left(\boldsymbol{h}_{j} \mid \boldsymbol{h}_{i}\right) p(hj​∣hi​)，既然训练参数矩阵 W s \mathbf{W}_{s} Ws​的目的是让对齐的邻接点的表示尽可能相似，那么目标函数可以用下面的：
L w = ∑ ( r , t ) ∈ L ∥ g r w − g t w ∥ L 1 (14) L_{w}=\sum_{(r, t) \in \mathbb{L}}\left\|\boldsymbol{g}_{r}^{w}-\boldsymbol{g}_{t}^{w}\right\|_{L_{1}} \tag {14} Lw​=(r,t)∈L∑​∥grw​−gtw​∥L1​​(14)
  作者的模型在预训练以后就是端到端的训练，期间使用式子11作为目标函数，每50个周期就使用式子14调整参数 W s \mathbf{W}_{s} Ws​。

6. 实验分析

数据集：DBP15K和DWY100K

  其数据大致情况如下，同时作者为了验证其模型的性能，构造了一个稀疏的数据集S-DBP15K：

  作者将其他语言的文本通过谷歌翻译成英文，相当于在同一空间进行实体的表示学习。同时为了验证其提出模块重要性，作者对齐模型进行部分的删减，形成变形对照实验，具体的详细参数设置可以阅读论文。其实验结果如下：

  通过上述的实验，可以看到实验结果有很大的提升，而且在作者自己构造的稀疏数据集上面还依旧表现非常的好。同时作者论文后续的分析部分其实很不错，对于不同的部分选取的原因加以了非常清晰的解释，后续的Impact of neighborhood sampling strategies、Impact of neighborhood sampling size、How does the neighborhood matching module work这三个部分对其模型很具有解释性，同时其丰富的实验验证了其理论，推荐大家详细阅读，在此就不具体介绍了。