简介
题目：《Knowledge Graph Alignment Network with Gated Multi-hop Neighborhood Aggregation》
来源：AAAI-2020
链接：论文链接
代码：Code和Dataset
研究背景
由于GNN网络在识别同构子图上表现非常不错，因此应用于很多基于嵌入式的实体对齐方法。但是实际上不同KGs之间对应的实体对，其周围的邻域图结构一般不是相似的，这导致GNN不能准确进行识别。如图1：
上图中指向Kobe Bryant的两个实体的邻域是不一致的，邻居实体集合也是不同的（有数据显示大部分对齐的实体对都具有不同的邻域）。要对齐的实体具有不同的邻域结构，使用GNN就容易导致为这些实体生成不同的表示。
本文为解决这个问题，提出了AliNet，希望通过引入远距离的邻居来缓解子图的异构性，同时还引入了注意力机制来有选择地择取远距离邻居，进而减少噪音，然后引入了门机制来整合直连邻居和远距离邻居的信息，最后还设计了一个关系损失函数去改善实体表示同时让AliNet能够更好地捕获一些如三角形关系结构等的信息。
预备知识
GNNs
在GNNs中，节点的表示一般通过迭代邻接节点的特征向量来获取的，不同的聚合方式会到导致不同的GNNs变型。
- GCN：其中比较受欢迎的一种变型就是vanilla GCN(Kipf and Welling 2017)，其节点i的第l层表示如下：
- R-GCN：Conventional GNNs只考虑节点的连接性方面，而忽略了边的标签性质。R-GCN (Schlichtkrull et al. 2018)依靠对于不同的边设置不同的权值来解决这个问题。
Entity Alignment of KGs
将给定的KG记为${G} = ( \mathcal {E} , \mathcal {R} , \mathcal {T} )$，三个元素分别表示实体集合、关系集合以及三元组集合，其中$\mathcal {T} = \mathcal {E} \times \mathcal {R} \times \mathcal {E} $。针对两个KG间的实体对齐问题，给定两个KG：$\mathcal {G}_1 = ( \mathcal { E }_1, \mathcal {R}_1, \mathcal {T}_1 )$和$\mathcal {G}_2 = ( \mathcal {E}_2, \mathcal {R}_2, \mathcal {T}_2 )$，然后给定部分预对齐的种子实体对：$\mathcal{A }^{ + } = { { (i, j) \in \mathcal { E}_1 \times \mathcal {E}_2 | i \equiv j} }$，其中$ \equiv $表示对齐关系。这一任务的目的是通过实体的嵌入，找出剩余对齐的实体对。
GNNs for Entity Alignment
目前基于GNN的实体对齐方法有：GCNAlign(Wang et al. 2018)、GMNN (Xu et al. 2019b)、 MuGNN(Cao et al. 2019)、RDGCN (Wu et al. 2019) 和AVR-GCN(Ye et al. 2019)。GCN-Align和GMNN是基于vanilla GCN设计的；RDGCN引入了对偶的关系图以增强vanilla GCN；AVG-GCN使用类似TransE的特定关系的translation操作，对R-GCN进行了扩展。在聚合之前，使用关系向量从尾实体translate成头实体的表示。作者认为针对特定关系的translation和R-GCN需要训练的参数量太大，计算成本高。而且上述模型均没有考虑到KG结构的异构问题。MuGNN模型注意到结构的不完整性，提出了基于规则的知识补全和多通道实体对齐的两种方法以缓解模式的异质性问题，然而其学习到的规则依赖于关系对齐。
以上分析都是针对已有的模型的总结，接下来讲解一些图特征对实体对齐的作用。
- Isomorphic structures are beneficial
对于同构结构的图，在已知预先对齐的邻接节点的情况下，其相应的节点的表示是相同的，那么我们分析考虑一种自由一层的GCN网络，采用mean-pooling方式进行聚集，在上图中的（i）情况下，例如：$h_a^{(0)}=h_{a^{\prime}}^{(0)}$，$h_b^{(0)} =h_{b^{\prime}}^{(0)}$，$h_d^{(0)}=h_{d^{\prime} }^{(0)}$，在理想情况下也有$\mathbf{h_a^{(1)}=h_{a^{\prime}}^{(1)}}$，$\mathbf{h_b^{(1)} =h_{b^{\prime}}^{(1)}}$，$\mathbf{h_d^{(1)}=h_{d^{\prime}}^{(1)}}$。通过$\mathbf{h_b^{(1)}=\sigma(W^{(1)}} (\mathbf{h_b^{(0)}+h_a^{(0)}}+\mathbf{h_c^{(0)})/3)}$和$\mathbf{h_{b^{\prime}}^{(1)}} =\sigma(\mathbf{W^{(1)}(h_{b^{\prime}}^{(0)}}+\mathbf{h_{a^{\prime}}^{(0)}+h_{c^{\prime}}^{(0)})/3)}$得到$\mathbf{h_c^{(0)}=h_{c^{\prime}}^{(0)}}$。这就表明给定部分对齐的邻居的时候，实体间的对齐信息可以在不同的GNN层中以及同构网络中传播。实际上这种理想情况很少，大多数情况下网络为异构网络如（ii）所示。
- Only structures are not enough
传统的GNN仅依赖于结构是不可靠的。比如一些三角形结构，如图（iii）中所示，通过聚合以后，会导致a=b的情况，实际上实体a和实体b是不同的实体。后续的R-GCN虽然考虑了关系，但是依赖于关系对齐这个前提，如果两个KGs中关系没有提前对齐则会导致实体对齐的信息不能顺序的传播。
- Compensation with distant neighborhood and relations
实际中，对齐实体对的邻居结构通常会是远近的混合形式，如图（iv）所示，为了减少异构带来的干扰，作者将远距离邻居考虑进去，相当于丰富了要对齐的实体周围的子图结构。但是不是所有邻近节点都是有用的，所以引入了注意力机制进行有所选择。为了进一步加强AliNet的表现，在不引入关系向量的情况下考虑关系的语义信息。
模型分析
在AliNet中，通过门机制来聚合K近邻的相关信息（one-hop为直连的，two-hop为间隔一个的），下本将以k=2举例来讲解，其k可以取更大的值。整体网络如下图：
Gated Multi-hop Neighborhood Aggregation
one-hop的节点，即直连的节点，对于GNNs网络中实体的的特征获取是非常重要的。作者对这些节点的表示，使用了vanilla GCN的层，其表示如上面方程式（1），表示为$\mathbf h_{i,1}^{(l)}$。虽然有L 层的GCN可以捕获L-hop的邻接信息，但是这的传播是低效的。
作者对于k=2的邻接点整合方程如下：
$$
\mathbf h_{i,2}^{(l)} \space = \space \sigma(\sum_{j\in N_2(i) \cup{i}}\alpha_{ij}^{(l)}W_2^{(l)}h_j^{ (l-1)}) \tag 3
$$
其中j为k=2的邻接节点，$\alpha_{ij}^{(l)}$ 是实体i和其邻接点j的一个可以学习的注意机制的权重，而 $W_2^{(l)}$ 是一个权重矩阵。受神经网络中跳跃连接（skip connections）的启发，作者提出使用门机制以结合1-hop邻居和2-hop邻居。实体i在第l层的隐层表示: $\mathbf{h_i^{(l)}}$计算如下：
$$
h_i^{(l)} = g(h_{i,2}^{ (l) } ) \cdot h_{i,1}^{(l)}+(1-g(h_{i,2}^{(l)}))\cdot h_{i,2}^{(l)} \tag 4
$$
其中$g(h_{i,2}^{(l)}) = \sigma(Mh_{i,2}^{(l)}+b)$作为门机制去整合one-hop与two-hop的节点。
Attention for Distant Neighborhood
远距离的邻接点的数目与其直连的节点的数目成指数关系。当然不是每个远距离节点都是有用的。对于k=2的聚合方式，我们得计算权重来强调有用的邻节点。GAT对每个注意力函数中的实体应用了一个共享的线性变换。然而，KG中的中心实体和其邻居可能是非常不同的，这样的共享变换会对区别它们带来负影响。因此作者使用了两个矩阵来进行线性变换，然后用softmax函数得到权重参数：
$$
c_{i j}^{(l)}=LeaklyReLU[ (M_1^{ (l) }h_i^{l})^T(M_2^{(l)}h_j^{l}) ] \tag 5
$$
$$
\alpha_{ij}^{(1)}=softmax_j(c_{ij}^{(1)})=\frac{exp(c_{ij}^{(1)})}{\sum_{n\in N_2(i) \cup {i}}exp(c_{ij}^{(l)})} \tag 6
$$
Contrastive Alignment Loss
作者最小化contrastive alignment loss函数让对齐的实体对距离尽可能小，而不对应得到实体对距离尽可能大。
$$
L_{1} = \sum_{(i,j)\in A^{+}}||h_i-h_j|| + \sum_{(i^{\prime},j^{\prime})\in A^-} \alpha_1{\lbrack \lambda-\vert \vert h_i^{\prime}-h_j^{\prime} \vert\vert \rbrack_+} \tag 7
$$
其中$A^{-}$由随机替换原先对齐的实体对的负样本集， $\lbrack\cdot\rbrack_{+}$ 表示 $max(0,\cdot)$ 。一般会用最后一层的结果表示实体，然后每一层的都传播了对齐的信息，因此我们使用所用的隐藏层的信息表示实体：
$$
h_i=\bigoplus_{l=1}^{L}norm(h_i^{ (l) } ) \tag 8
$$
其中 $\oplus$ 是并接操作， $norm(\cdot)$ 是 $L_2$ 正则化操作。
Relation Semantics Modeling
作者认为对于图中提供的语义关系，很本能地应该利用这些信息，上面讨论的R-GCN需要高度相似的图结构以及对其的关系。这里作者借用TransE的思想，为了避免参数过多，作者没有引入针对特定关系的嵌入。关系r的表示$\mathbf{r}$，可以通过和它相关的实体嵌入得到：
$$
r = \frac{1} {T_r} \sum_{(s,o) \in T_r}(h_s-h_o) \tag 9
$$
其中 $T_r$ 是subject-object实体对的关系r，然后最小化下面的关系损失函数：
$$
L_2=\sum_{r\in R} \frac {1} {T_r} \sum_{(s,o)\in T_r}(h_s-h_o-r) \tag {10}
$$
Implementation
- Objective
最终的目标函数为两个损失函数的组合，其中$\alpha$为超参数，使用Adam optimizer优化：
$$
L = L_1+\alpha_2L_2 \tag {11}
$$
所有可学习的参数都使用Xavier initialization (Glorotand Bengio 2010)的初始化
- Generalization to k-hop neighborhood
这里作者整合邻接的信息的时候使用$\rho(h_{i,1}^{(l)},h_{i,2}^{(l)})$作为k=2的整合方程(4)。我们可以用k-1个门机制函数去整合k邻的信息：
$$
h_{i}^{l} = \rho_{k-1} ( \cdots \rho_2 ( \rho_1 (h_{i,1}^{ (l) },h_{i,2}^{ (l) }),h_{i,3}^{ (l) }) \cdots) \tag {12}
$$
- Neighborhood augmentation
作者在这里为了进一步缓解KGs之间的异构性，对于预先对齐的实体i和j之间有边$e_{i,j}$，而在另一个图中对应对齐的实体i和实体j之间没有相应的边，则我们加上这样的边来缓解图之间的异构性。
- Alignment prediction
对于实体对齐预测部分，采用了大多数采用的方法，计算另一个图中所有实体和本图中实体之间的距离的最小值作为对齐的预测值。
实验分析
数据集
作者采用的数据集与大多数实体对齐采用的实体集大致一样。
Comparative Models
基于嵌入式的实体对齐模型：MTransE (Chen et al. 2017)、IPTransE (Zhu et al.2017)、JAPE (Sun, Hu, and Li 2017)、 AlignE (Sun et al. 2018)、GCN-Align (Wang et al. 2018)、SEA (Pei et al. 2019)、RSN(Guo, Sun, and Hu 2019)、MuGNN (Cao et al. 2019)
基于知识图谱嵌入的模型：（一般用于链接预测）TransH (Wang et al. 2014), ConvE (Dettmers et al. 2018) 、RotatE (Sun et al. 2019)
基于GCN的变形模型：GCN (Kipf and Welling 2017)、GAT (Velickovic et al. 2018) 、R-CGN(Schlichtkrull et al. 2018)。（这些模型作者重新调整相关设置，以便进入和作者模型同一管道中）
基于AliNet的变形模型：AliNet (w/o rel. loss)不使用优化关系损失、AliNet (w/o rel. loss & augment.)既不优化关系损失也不进行邻接的整合
上述三种不同类型的模型就是作者比较的对象，同时作者对自己模型进行变型，分别看各个部分的效果。
Implementation Details
作者使用网格搜索法进行参数优化，具体的详情可以见论文叙述。
Main Results
同时作者分析中，分别对整合的策略，对于网络层数以及选择的k值分别进行对比实验：
作者最后还分析了由于实体的表达是由多层网络聚合而成的，然后作者分别用每层网络来表示实体，最后结果也与作者原先分析的大致相似，整合多层网络效果更好。
通过上边的比较分析，可以看到到作者提出的AliNet模型效果非常好。在考虑大多数数据集的结构都不是相似的情况下，提出了对应的解决方案，对于不同模块的处理作者花了很多心思，最后通过对比实验也验证了其理论。
参考资料：