实体对齐论文总结

Posted by Pelhans on March 18, 2019

学习中…

概览

实体对齐(Entity alignment) 就是找到两个知识图谱中相同的等价实体。它们可能有不同的表面形式或者不同的属性,因此单纯的基于表面形式匹配是不够用的。

用公式定义实体对齐任务的话。首先我们用 \(G = (E, R, A, T_{R}, T_{A})\)表示知识图谱,其中\(E, R, A\) 表示其中的实体、关系和属性。 \(T_{R}\) 是关系三元组 \(E -- R -- E\) 。\(T_{A}\) 是属性三元组 \(E -- A -- V\) 。已知有知识图谱 G1 和 G2,目的是找到两个图谱中的等价实体集合 \(S {(e_{i1}, e_{i2})}\)。

这个方向受图神经网络的发展的福利,近期是一个大热门。这里对我接触到的论文做一个记录,防止忘记。

数据集

BBP15K

比较常用的数据集,南京大学提出的,包含 ZH-EN, JA-EN, FR-EN 三种跨语言的实体对齐语料,其中细节如下表所示

评价指标

目前看到的是 Hits@N, 表示排名前 k 的候选中正确对齐的实体的比例。

论文笔记

Cross-lingual Knowledge Graph Alignment via Graph Convolutional Networks

早期的论文,用 GCN 做实体对齐。 GCN 模型由一系列的 GCN 层堆叠得到。公式表述为

\[H^{l+1} = \sigma(\hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} H^{l}W^{l})\]

其中 \(\sigma\) 是激活函数,A 是 邻接矩阵,\(\hat{A} = A + I\) ,\(\hat{D}\) 时度矩阵, \(W^{l} \in R^{d^{l}\times d^{l+1}}\) 是第 l 层的权值矩阵, \(d^{l+1}\) 是新特征矩阵的维度。

论文结构如下图所示

公式很经典,是比较经典的 GCN 卷积核。相当于聚集周边节点的信息到中心节点。但对于实体对齐任务,除了节点信息,网络的结构信息也很重要。因此坐着对 H 做了手脚,将其分为结构向量\(h_{s}\) 和 属性向量\(h_{a}\) 两部分。初始输入时, \(h_{s}^{0}\) 采用随机初始化并随着训练进行更新,\(h_{a}^{0}\) 用 实体向量进行初始化,在后续训练中固定不更新。这样我们就可以得到新的 GCN 公式:

\[[H_{s}^{l+1};H_{a}^{l+1}] = ReLU(\hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} [H_{s}^{l}W_{s}^{l}; H_{a}^{l}W_{a}^{l}] )\]

在多轮更新后,对于两图谱中的给定实体节点 \(e_{i}\) 和 \(v_{j}\),用加权的 L1 距离度量实体间相似度:

\[D(e_{i}, v_{j}) = \beta\frac{f(h_{s}(e_{i})), h_{s}(v_{j})}{d_{s}} = (1-\beta)\frac{f(h_{a}(e_{i}), h_{a}(v_{j}))}{d_{a}}\]

其中 \(f(x,y) == || x - y||_{L1}\),\(d_{s}\) 和 \(d_{a}\) 是结构和属性的嵌入维度, \(\beta\) 是超参。具体的玩过参数设置如下图所示:

但上面公式中有一个问题:普通的邻接矩阵 A 没法处理关系,因此坐着提出一个 A 的构造方法,对于 A中每个元素 \(a_{ij}\) ,有

\[fun(r) = \frac{Head_Entities_of_r}{Triples_of_r}\] \[ifun(r) = \frac{Tail_Entities_of_r}{Triples_of_r}\] \[a_{ij} = \sum_{<e_{i}, r, e_{j}>\in G} ifun(r) + \sum_{<e_{j}, r, e_{i}>\in G}fun(r)\]

其中 Head_Entities_of_r 表示 关系 r 中头实体的数量, Tail_Entities_of_r 表示 关系 r 的尾实体数量。 Triples_of_r 表示关系 r 的三元组的数量。 \(a_{ij}\) 表示第 i 个实体对第 j 个实体的影响。

损失函数采用 margin-based ranking loss,这个在实体对齐任务中比较常用:

\[L_{s} = \sum_{(e,v)\in S}\sum_{(e^{'}v^{'}\in S^{'}_{e,v})}[f(h_{s}(e), h_{s}(v)) + \gamma_{s} - f(h_{s}(e^{'}), h_{s}(v^{'}))]_{+}\]

其中 \([]_{+}\) 表示 ReLU 激活。最终再 BBP15K 数据集上的表现如下表所示,其中 JAPE 和 MTransE等都是基于向量嵌入的方法,可以看出 Hits@1 有比较大的提升。在所有的基线中,JAPE是最强的;这可能是因为它同时使用关系和属性三元组的能力,以及它所依赖的关系和属性的额外对齐。图方法在两个数据集上取得了比JAPE更好的结果;尽管JAPE比我们的方法更好,但是它们的结果之间的差异很小。如果两个KG之间没有现有的关系和属性对齐,图方法将比 JAPE 有明显的优势。

Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network

该论文引入主题实体图,一个实体的局部子图,用它们的上下文信息来表示实体。从这一观点出发,知识库对齐任务可以表述为一个图匹配问题,并进一步提出了一种基于图注意的解决方案,该方案首先匹配两个主题实体图中的所有实体,然后对局部匹配信息进行联合建模,得到一个图级别的匹配向量。

具体来说,我们首先利用图卷积神经网络(GCN)对两个图进行编码,例如G1和G2,得到每个图的实体嵌入列表。然后,我们使用注意匹配方法将G1(或G2)中的每个实体与G2(或G1)中的所有实体进行比较,该方法为G1和G2中的所有实体生成跨语言的KG感知匹配向量。因此,我们应用另一个GCN在整个图中传播局部匹配信息。这将为用于最终预测的每个主题图生成一个全局匹配向量。背后的动机是,图卷积可以联合编码所有的实体相似性,包括主题实体和它的邻居实体,成为一个匹配向量。

论文有 github 代码

网络结构如下图所示:

首先是主题实体图的构造。为了构建主题图,首先收集主题实体的一跳邻居实体,得到一组实体 \({e_{1}, \dots,e_{n}}\),它们是图的节点。然后,对于每个实体对\((e_{i},e_{j})\),如果ei和ej通过关系(比如r)直接连接在KG中,则我们在主题图中它们对应的节点之间添加一条有向边。注意,我们没有用ei和ej在KG中保持的r来标记这个边,而只是保持r的方向。在实践中,我们发现这种策略显著地提高了效率和性能。

接下来介绍网络,整个网络分为三层:

  • 输入表示层:
    • 对于每个节点,用 LSTM 处理得到向量 \(a_{v}\)
    • 将邻居节点采用 FFN 进行聚合,得到单一向量 \(h_{N,in}^{k-1}\),其中 k 表示迭代次数。
    • 将聚合后的向量和聚合前的向量进行拼接:\([h_{u;in}^{k-1}; h_{N;in}^{K}]\),拼接后的向量用 FFN 处理,得到节点的单一向量表示
    • 将 in 换成 out 进行同样的过程,得到节点的出度表示
  • 节点级别的(Local) 匹配:
    • 类似于attentive 匹配那种,计算G1中节点对G2 中所有节点的相似性,和 G2中节点对 G1中每个节点的相似性。 \(a_{ij} = cosine(e_{i}^{1}, e_{j}^{2})\)
    • 对 G2 中的每个节点加权求和,得到 G1 中节点的新表示。 \(\hat{e}_{i}^{1} = \frac{\sum_{j=1}^{|G_{2}}a_{ij}*e_{j}^{2}}{\sum_{j=1}^{|G_{2}|}a_{ij} }\)
    • 计算匹配向量 \(m_{i}^{att} = f_{m}(e_{i}^{1}, \hat{e}_{i}^{1})\) 和 \(m_{j}^{att}\)
  • 图级别(全局)匹配层:
    • 局部匹配状态,不足以度量全局图的相似性。例 如,许多实体只有很少的相邻实 体共同出现在G1 和G2中。对于这 些实体,利用局 部匹配信息的模 型很可能会错误 地预测这两个图 描述的是不同的 主题实体,因为 G1和G2中的大多 数实体在其嵌入 空间中并不紧 密。
    • 设计一个图上 的GCN2(具有足够数量的跳数),将局部匹配的信息传播到整个图中。这样就能够对整个图对之 间的全局匹配 状态进行编 码。然后,我 们将这些匹配 表示形式输入 到完全连接的 神经网络中, 并应用元素最 大和平均池方 法生成固定长 度的图匹配表 示形式。
  • 预测层:用一个两层的FFN 来聚合匹配向量并用 Softmax 进行预测。

该模型的结果如下图所示:

可以看出图匹配方法明显优于所有基线,这表明主题实体的全局上下文信息对于建立它们的相似性很重要。同时表面形式是 KG 对齐的一个重要特征。跳数等于3 时效果好。

图匹配层增强了我们的模型处理两个KG中大多数邻居不同的实体的能力。对于这样的实体,虽然大多数局部匹配 信息表明这两个实体是不相关的,但是图匹配层可以通过在整个图中传播最相关的局部匹配信息来缓解这种情况。

将关系标签合并为不同的节点,将实体节点连接到主题图中不仅会降低模型的性能,而且会降低模型的效率。 我们认为这是因为(1)关系标签在数据集中被表示为抽象符号,这提供了关于关系的非常有限的知识,使得 模型很难在两个图谱内学习它们的对齐;(2)合并关 系标签可能会显著增加主题实体图的大小,这需要更大 的跳数尺寸和运行时间。

wang er al(2018)就是开篇的模型,可以看出,对于节点的充分匹配交互可以大幅度提升模型性能。

Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs

论文提出关系敏感的对偶图卷积神经网络 (RDGCN ) 。它通过原始图与其对偶关系图之间的密切交互来融合关系信息, 并进一步捕获相邻结构以学习更好的实体表示。

实体链接任务,一开始是 TransE那种直接向量嵌入,缺点是KG受到假设头+关系尾的约束。 这种强有力的假设使得模型在多关系图中捕获更复杂的关系信息效率低下。比如三角关系的存在,如下图所示,当三角关系存在时,将会导致内在的矛盾,从而损伤性能。

论文认为 GPGCNN (Dual-Primal Graph CNN) 是一种可行的方案,DPGCNN交替对图及其对偶图进行卷积操作,其顶点对应于原始图的边缘,并迭代地应用图注意机制以使用其双图来增强原始边缘表示。

与GCN和R-GCN(Relation GCN)相比,DPGCNN可以更好地探索复杂的边缘结构并产生更好的KG表示。R-GCN为每个关系提供一个权重矩阵,但KG中往往有上千种关系,因此资源消耗太大。

本论文基于DPGCNN进行扩展。这样做要求我们找到一种更好地近似关系表示和刻画不同KG关系之间关系的方法。论文通过扩展DPGCNN来开发一个加权模型来解决这个问题,并探索以实体名称初始化的头/尾表示作为代理来捕获关系信息,而不需要过多的模型参数,这些参数通常很难训练。论文主要贡献是允许再实体表示中融入更加复杂的关系;扩展 highway gates 到 GCN 中。

模型的网络结构如下图所示:

模型流程为:

  • 首先构造其对偶关系图,其顶点表示原始图中的关系
  • 然后,我们利用图注意机制来鼓励对偶关系图和原始图 之间的相互作用。
  • 原始图中得到的顶点表示随后被输入到GCN层,并带有 highway gate,以捕获相邻的结构信息。
  • 最终的实体表示将用于确定是否应对齐两个实体。

接下来,分开介绍。

对偶图的构建:

  • 先把G1和G2合在一起(还是两个离散的图)
  • 而后构建对偶图,所谓对偶图是指以关系为节点,若两个关系共享了相同的Head或者tail,则在关系节点间添加边。
  • 更进一步,还在边上添加了权重,权值为两关系共享head的概率和共享tail的概率
  • 构造对偶图的开销与原始图中关系类型的数量成正比
\[w_{ij}^{r} = H(r_{i}, r_{j}) + T(r_{i}, r_{j})\] \[H(r_{i}, r_{j}) = \frac{H_{i}\cap H_{j}}{H_{i}\cup H_{j}}\] \[T_{r_{i}, r_{j}} = \frac{T_{i}\cap T_{j}}{T_{i}\sup T_{j}}\]

原始图和对偶图的交互作用:

  • 应用图注意机制(GAT)迭代地获得对偶关系图和原图的顶点表示,其中注意机制有助于促进两个图之间的交互。
  • 每个对偶-原图交互包含两层:对偶attention层和原图attention层。
  • 在两个图上叠 加多个交互以 相互改进。

对偶 attention 层:

\[\hat{x}_{i}^{r} = ReLU{r}(\sum_{j\in N_{i}^{r}}\alpha_{ij}^{r}x_{j}^{r})\] \[\alpha_{ij}^{r} = \frac{exp(LeakyReLU(w_{ij}^{r}a^{r}[c_{i}; c_{j}]))}{\sum_{k\in N_{i}^{r} exp(LeakyReLU(w_{ik}^{r}a^{r}[c_{i}; c_{k}]))}}\]

比较典型的 attention。其中 \(x^{r}\) 为对偶图中的一个顶点表示, \(c_{i}$ 是原始图中关系\)r_{i}\(的表示,不过由于数据量的限制,需要用\) c_{i} = [\frac{\sum_{k\in H_{i}}\hat{x}{k}^{e}}{H{i}}; \frac{\sum_{l\in T_{i}}\hat{x}{l}^{e}}{T{i}}] \(。\) a_{ij}^{r}$$ 是 FFN,因此这个 attention 是用 全连接计算相似度。唯一比较不正常的是,相似度得分不是在对偶图上算的,而是计算原始图中关系的相似度。

原始图 attention 层:

\[\tilde{x}_{q}^{e} = ReLU(\sum_{t\in N_{q}^{e}}\alpha_{qt}^{e}x_{t}^{e})\] \[\alpha_{qt}^{e} = \frac{exp(LeakyReLU(FFN(\tilde{x}_{qt}^{r})))}{\sum_{k\in N_{q}^{e}}exp(LeakyReLU(FFN(\tilde{x}_{qk}^{r})))}\]

其中 \(\tilde{x}_{qk}^{r}\) 是对偶图中的关系 \(r_{qt}\) 的表示。最终原始图的表示为

\[\hat{x}_{q}^{e} = \beta_{s}*\tilde{x}_{q}^{e} + x_{q}^{e init}\]

其中 \(x_{q}^{e init}\) 是根据 name 得到的初始表示,包含重要的词义信息,因此最终要加上。

为了更充分利用结构信息,再 GAT 后加了两层的 GCN + highway 对原始图进行学习。GCN 用的是经典的

\[X^{l+1} = \epsilon(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X^{l}W^{l} )\]

为了保留有用信息,控制噪声得累积,使用 highway network:

\[T(X^{l}) = \sigma(X^{l}W_{T}^{l} + b_{T}^{l})\] \[X^{l+1} = T(X^{l}) * X^{l+1} + (1-T(X)^{l})*X^{l}\]

最终利用 GCN 中对应的实体节点信息计算实体间距离:

\[d(e_{1}, e_{2}) = ||\hat{x}_{e1} - \hat{x}_{e2}||_{L1}\]

损失函数还是采用 max-margin loss。最终模型效果如下: