1 导引

我们在上一篇博客《知识图谱实体对齐1：基于平移(translation)嵌入的方法》中介绍了如何对基于平移嵌入+对齐损失来完成知识图谱中的实体对齐。这些方法都是通过两个平移嵌入模型来将知识图谱G$1_{}$和${\mathcal{G}}_2$的重叠实体分别进行嵌入，并加上一个对齐损失来完成对齐。不过，除了基于平移的嵌入模型之外，是否还有其它方式呢？

答案是肯定的。目前已经提出了许多基于GNN的实体对齐方法^[1]，这些方法不仅采用GNN捕捉更多的实体结构化信息，还通过诸如参数共享、参数交换等方式在embedding模块中就使实体的embeddings尽可能统一到一个向量空间。

基于GNN的方法可以被分为基于GCN(graph convolutional network)的和基于GAT(graph attention network)两类，它们常常使用实体的邻居知识来对知识图谱的结构进行编码，大多数邻居及被做为嵌入模块的输入特征。因为这里存在一个假定，即对齐的实体将有相似的邻居。大多数基于GNN的方法在训练中只使用实体来做为对齐种子，而不是关系来做为对齐种子。

2 基于GNN的方法

2.1 GCN-Align

本文是第一篇采用GNN来进行实体对齐的工作^[2]。GCN-Align使用两个GCN来将${\mathcal{G}}_1$和${\mathcal{G}}_2$的实体嵌入到一个统一的向量空间中（这两个GCN使用共享权重矩阵）。

（注：原论文除了实体embeddings，还还有个属性embedings，我们这里从简省略）
这里${\mathit{H}}^{(l+1)}$是实体的embeddings，${\mathit{W}}^{(l)}$是其对应的权重，A^=A+I$\hat{\mathit{A}}=\mathit{A}+\mathit{I}$意为带自环的权重矩阵，$\hat{\mathit{D}}$意为$\hat{\mathit{A}}$的节点度矩阵（用于归一化使用）。

不过GCN-Align和GCN有所不同，GCN-Align在计算$a\in \mathbb{A}$时还考虑了不同的关系谓词。新的邻接矩阵计算如下：

这里函数$g_h(r)$和$g_t(r)$计算了由关系r$r$连接的头实体和尾实体的数目再除以含有关系r$r$的实体数量。T$\mathcal{T}$为知识图谱中所有元组的集合。$(e_j,r,e_i)$和$(e_i,r,e_j)$都是KG中的元组。函数$g_h(r)$和$g_t(r)$分别计算关系r$r$所连接的头实体和尾实体数量。这样，邻接矩阵$\mathit{A}$就有助于对embedding信息如何在实体间传递进行建模。

然后，GCN-Align的训练也是由最小化间隔损失（参见我们上一篇博客《知识图谱实体对齐1：基于平移(translation)的方法》）来完成，其alignment score function定义为：

这里$h(\cdot )$表示维度为d$d$的实体嵌入。

整个网络的架构如下：

2.2 HGCN

HGCN^[3]在实体嵌入的过程中隐式地利用关系的表示来改善对齐过程。为了包含关系信息，HGCN同时学习实体和关系谓词的embeddings，

其整个包含embedding和align模块的框架如下：

本文提出的框架可分为以下的三个阶段：
Stage 1 使用GCN的变种Highway-GCN来将实体嵌入到统一的向量空间。这里直接将${\mathcal{G}}_1$和${\mathcal{G}}_2$视作一个图$G_a$，然后使用一个统一的GCN来获得$G_a$的实体嵌入：

我们这里采用逐层的highway gates（高速门）来建立Highway-GCN(HGCN)模型。逐层的highway gates用于控制GCN网络中的前向传播，写为以下的函数$T$的形式：

这里${\mathit{H}}^{(l)}$是$l^{th}$层的输出，$(l+1{)}^{th}$层的输入。⊙$\odot$是逐元素乘。

这样，HGCN分别计算两个KG的embeddings，并在训练中仍然使用上面所提到过的的alignment score function falign(e1,e2)$f_{\text{align}}(e_1,e_2)$+间隔损失函数。

Stage 2 基于关系谓词的头实体和尾实体的表征来获得其embeddings。该阶段先分别计算所有连接关系谓词的头实体和尾实体的平均embeddings，接着这两个均值embeddings会在一个线性变换之后拼接起来做为关系的embeddings，这样就可以对跨知识图谱的关系进行对齐。

Stage 3 再次使用Highway-GCN（其输入为Stage 1中得到的embeddings和与该实体有关的关系谓词embeddings之和的拼接）做为共同的实体embeddings，然后alignment模块再次使用alignment score function + 间隔损失将两个知识图谱在Highway-GCN的输出映射到统一的向量空间。

2.3 GMNN

GMNN^[4]将实体对齐问题形式化了为两个图之间做匹配的问题。传统的图匹配问题会通过对单语言知识图谱的事实进行编码，将每个知识图谱的实体投影到低维子空间。然而，对于跨语言问题，一些实体在不同的语言中可能存在不同的知识图谱事实，这可能导致其在在跨语言的实体embeddings中编码的信息具有差异性，从而使得这类方法难以对实体进行匹配。

如上图展示了我们对$e_0$和$e_0^{\prime }$进行对齐的实例。但是在它们周围的邻居中只有一个对齐的邻居。这种方法得匹配只有很少的邻居的实体非常困难，因为缺乏足够的结构化信息。

为了解决这个缺点，作者提出了topic entity graph（主题实体图）来表征知识图谱中实体的上下文信息。不同于之前的方法使用实体embeddings来匹配实体，作者将这个任务建模为在topic entity graph之间进行图匹配。每个实体都对应一个topic entity graph（由相隔一跳的邻居和对应的关系谓词组成），这样的一个图能够表征实体的局部上下文信息。

该论文提出的由四层组成，包括输入表示层、node-level匹配层，graph-level匹配层和预测层。如下图所示：

输入表示层使用GCN将两个topic graph进行编码并获得实体的embeddings。

之后node-level匹配层会为每个实体计算其对应匹配向量。设有G1${\mathcal{G}}_1$和G2${\mathcal{G}}_2$两个topic graph，ei$e_i$为图G1${\mathcal{G}}_1$中的实体，首先计算e¯i${\overline{e}}_i$如下：

这里${\alpha }_{i,j}$是实体i$i$和${\mathcal{G}}_2$中的实体j$j$之间的余弦相似度。可见${\overline{\mathit{e}}}_i$即为另一个topic graph中所有实体embeddings的attention加权和。 接着，使用multi-perspective sine matching functionfm$f_m$来计算${\mathcal{G}}_1$和${\mathcal{G}}_2$所有实体的匹配向量，如下式所示：

这里$\mathit{m}=f_m({\mathit{v}}_1,{\mathit{v}}_2;\mathit{W})$，其中$m_k\in \mathit{m}$是来自$k$个perspective的matching value，它根据两个向量加权后的余弦相似度进行计算：

这里${\mathit{v}}_1$和${\mathit{v}}_2$是d维向量，$\odot$是逐元素乘法，${\mathit{w}}_k$是$\mathit{W}$的第k$k$列，用于控制第k个perspective并将不同的权重加在d个不同的维度上。

至此，获得的是局部的node-level的匹配向量。然而想要度量图的相似度，还需要获得graph-level的一个整体匹配向量。于是接下来将计算好的匹配向量输入graph-level匹配层的GCN，在这个过程中局部匹配信息会被传播。最后，GCN输出的新embeddings在经过逐元素最大/平均池化方法后会被送入一个全连接神经网络，以获得这个图的一个整体匹配表征。最后预测层将图的匹配表征作为softmax回归函数的输入来预测对齐实体。

2.4 MuGNN

MuGNN^[5]强调用于对齐的不同知识图谱之间的结构异质性，因为这种结构异质性会导致需要对齐实体embeddings之间的不相似性。为了调和${\mathcal{G}}_1$和${\mathcal{G}}_2$之间的结构异质性，MuGNN在嵌入模块中使用多通道GNN以编码多通道图。形式化地，多通道GNN如下图所示，假定这里为双通道MuGNN：

这里${\mathit{A}}_1$由self-attention决定，$a_{ij}$是从$e_i$到$e_j$的连接权值，如下所示：

$N_{e_i}$是$e_i$的邻居，$c_{ij}$是attention系数。

而${\mathit{A}}_2$通过降低互斥（exclusive）实体之间的连接权值来对互斥实体进行修剪。

这里${\mathcal{R}}_1$和${\mathcal{R}}_2$分别是${\mathcal{G}}_1$和${\mathcal{G}}_2$关系谓词的集合。当$(e_i,r_1,e_j)\in {\mathcal{T}}_1$时函数$\mathbf{1}(\cdot )=1$，否则为0。函数$\mathrm{sim}(r_1,r_2)$为关系谓词$r_1$和$r_2$之间的内积相似度。

之后MuGNN的alignment模块采用了普通alignment score function的变种将来自多通道GNN的${\mathcal{G}}_1$和${\mathcal{G}}_2$的embeddings统一到相同的向量空间，该变种采用了种子实体对齐损失和种子关系谓词对齐损失的加权和。

改论文的框架整体架构如下：

2.5 NMN

NMN^[6]也旨在解决不同知识图谱间的结构异质性。为了解决这个问题，该论文采用的方法同时学习了知识图谱的结构信息和邻居的差异，这样不同实体间的相似性就能够在结构异质性的情况下被捕捉。

为了学习知识图谱的结构信息，NMN的嵌入模块使用我们前面提到过的带有highway gates的GCN来对知识图谱的结构信息进行建模，其中将待对齐的${\mathcal{G}}_1=({\mathcal{E}}_1,{\mathcal{R}}_1,{\mathcal{T}}_1)$和${\mathcal{G}}_2=({\mathcal{E}}_2,{\mathcal{R}}_2,{\mathcal{T}}_2)$做为输入。这个模型先使用种子对齐实体+基于间隔的损失函数来进行预训练，以初步得到实体的embeddings；之后，再使用跨图匹配来捕捉邻居的差异，得到每个实体对应的的邻居表征；最后，NMN将实体embeddings和邻居表征进行拼接以获得最终用于对齐的embeddings，其对齐操作是通过度量两个实体embeddings之间的欧几里得距离来完成。

该论文所提出方法的框架示意图如下所示：

下面我们详细介绍它的步骤：

知识图谱结构嵌入 即常规的GCN实体对齐+嵌入模块，采用我们前面提到过的对齐损失。

邻居采样 本文认为与实体相隔单跳（one-hop）的邻居是进行实体对齐的关键依据。然而并非所有的邻居都对实体对齐有正向的贡献，为了选择正确的邻居，作者采用降采样的方式来对邻居实体进行筛选。给定实体ei$e_i$，它的邻居ei_j$e_{i\mathrm{\_}j}$被采样的概率为：

这里${\mathcal{N}}_i$为中心实体$e_i$的邻居的下标集合，${\mathit{h}}_i$和${\mathit{h}}_{i\mathrm{\_}j}$分别是实体$e_i$和$e_{i\mathrm{\_}j}$的embeddings，${\mathbf{\text{W}}}_s$是共享权重矩阵。

跨图邻居匹配 首先，对于${\mathcal{E}}_1$中的实体ei$e_i$，如直接将其采样后的邻居子图和每个${\mathcal{E}}_2$中候选实体的邻居子图进行两两比较，以选择最优对齐实体，则会带来巨大的计算开销。为了减少匹配开销，NMN采用了近似方法，为$e_i$从${\mathcal{E}}_2$中采样了一个候选对齐实体集合，对于${\mathcal{E}}_2$中的实体$e_j$，其被采样为$e_i$的候选对齐实体的概率为：

之后，在具体的跨图邻居匹配方法上，本文借鉴了李宇佳在ICML2019发表的经典工作^[7][8]。将邻居子图对做为输入，然后计算每个邻居实体的跨图匹配向量，这个向量度量了当前子图的邻居和另一个子图中邻居的匹配程度。形式化地说，设$(e_i,e_j)$为一个需要被度量的实体对（$e_i\in {\mathcal{E}}_1$，$e_j\in {\mathcal{E}}_2$），p和q分别i$e_i$和$e_j$的一个邻居。则邻居p的跨图匹配向量计算如下：

这里$a_{pq}$是注意力权重，${\mathcal{N}}_j^s$是实体$e_j$的采样邻居集合，${\mathit{h}}_p$和${\mathit{h}}_q$分别是$p$和q的embeddings。${\mathit{m}}_p$做为p的匹配向量，度量了${\mathit{h}}_p$和其在另一个子图中最近邻居之间的差异。接着，将邻居p原本的embeddings和之前得到的匹配向量${\mathit{m}}_p$进行拼接：

邻居聚合 最后，对实体$e_i$，需要将其邻居表征${\hat{\mathit{h}}}_p$进行聚合，其聚合方法采用李宇佳在ICLR 2016^[9]中提出的门控聚合：

接着，将实体$e_i$的embeddingsi${\mathit{h}}_i$与其邻居表征拼接来构建$e_i$的最终表征：

在实际训练时，NMN对齐模块的损失和预训练对齐的损失会累加在一起进行训练。

这里还需要提到的是，在邻居采样部分，计算邻居被采概率$p({\mathit{h}}_{i\mathrm{\_}j}\mid {\mathit{h}}_i)$时所用到的参数Ws${\mathbf{\text{W}}}_s$是需要训练的，但随机采样的过程是不可导的，这会导致${\mathbf{\text{W}}}_s$不可训练。因此本文每隔$50$个epoch，会采用加权聚合来得到“软”的邻居表征，并计算对齐损失以训练${\mathbf{\text{W}}}_s$。“软”的邻居表征计算公式如下：

这里${\alpha }_{ip}$是对邻居p的采样概率$p(\mathit{h}|{\mathit{h}}_i)$。具体的对齐损失函数与前面采样的一致。

2.6 CEA

CEA^[10]考虑实体之间对齐决策的依赖性。比如一个实体如果已经被对齐到某个实体，那么它就不太可能再被做为对齐目标使用。该网络使用结构化、语义和字符串信号来捕捉源知识图谱和目标知识图谱实体之间在不同方面的相似度，而这由三个不同的相似度矩阵来表征。特别地，这里的结构化相似度矩阵会经由GCN并使用使用余弦相似度来计算，语义相似度矩阵由单词的embeddings来计算，字符串相似度矩阵由实体名称之间的Levenshtein距离计算。这三个矩阵之后会融合为一个矩阵。CEA之后会将实体嵌入形式化为一个在融合矩阵上的经典稳定匹配问题来捕捉相互依赖的EA决策。

3 参考文献

[1] Zhang R, Trisedya B D, Li M, et al. A benchmark and comprehensive survey on knowledge graph entity alignment via representation learning[J]. The VLDB Journal, 2022: 1-26

[2] Wang Z, Lv Q, Lan X, et al. Cross-lingual knowledge graph alignment via graph convolutional networks[C]//Proceedings of the 2018 conference on empirical methods in natural language processing. 2018: 349-357.

[3] Wu Y, Liu X, Feng Y, Wang Z, Zhao D (2019b) Jointly learning entity and relation representations for entity alignment. In: EMNLP 2019

[4] Cross-lingual knowledge graph alignment via graph matching neural network. In: ACL 2019

[5] Cao Y, Liu Z, Li C, Liu Z, Li J, Chua TS (2019) Multi-channel graph neural network for entity alignment. In: ACL 2019

[6] Wu Y, Liu X, Feng Y, Wang Z, Zhao D (2020) Neigh-borhood matching network for entity alignment. In: ACL 2020

[7] Li Y, Gu C, Dullien T, et al. Graph matching networks for learning the similarity of graph structured objects[C]//International conference on machine learning. PMLR, 2019: 3835-3845.

[8] 《如何找到相似Graph？DeepMind提出超越GNN的图匹配网络》

[9] Yujia Li, Richard Zemel, Marc Brockschmidt, and Daniel Tarlow. 2016. Gated graph sequence neural networks. In Proceedings of ICLR’16.

[10] Zeng W, Zhao X, Tang J, Lin X (2020) Collective entity alignment via adaptive features. In: ICDE 2020