实体对齐文献阅读笔记

阅读实体对齐相关文献的笔记

1. Translating Embeddings for Modeling Multi-relational Data

如果一个三元组成立，则应该满足$\mathbf{h}+\mathbf{l}\approx\mathbf t$

即$d(\mathbf h+\mathbf l,\mathbf t)$ 尽可能小，而$d(\mathbf h'+\mathbf l,\mathbf{t'})$尽可能大

其中$\mathbf{h'\ t'}$表示不可能对齐的实体对，通过替换种子实体中头或尾实体为随机实体得到

所以就得到了上面的损失函数，$[x]_+$表示若$x>0$则取$x$，若$x<0$则取$0$,由此得到，如果$\gamma$较大则训练时间较长，因为需要较多时间让$\mathbf L$到达$0$，否则需要时间较短

最后使用随机梯度优化进行训练

2. A Joint Embedding Method for Entity Alignment of Knowledge Bases

在TransE的基础上，修改了损失函数

其中二范数接近于1可以避免通过最小化嵌入来最小化损失函数，这样就不是由于对齐而是由于嵌入的减小才导致的损失函数减小

矩阵M如下计算

3. Multilingual Knowledge Graph Embeddings for Cross-lingual Knowledge Alignment

采用传统TransE，但是损失函数重新定义$S_K=\sum\limits_{L\in\{L_i,L_j\}}\sum\limits_{(h,r,t)\in G_L}||\mathbf{h+r-t}||$

即直接利用所有三元组衡量嵌入的效果

• 这样做可以让单语种保留原有特性，因为单个语种的三元组只在自己内部训练
• 不同语言可以并行训练

对齐模块的损失函数

$S_A=\sum\limits_{T,T'\in\delta(L_i,L_j)}S_a(T,T')$

其中$S_a(T,T')$穷举所有种子三元组对

其中$S_a$包含5种变体

• 基于距离的坐标轴转换：$S_{a_1}=\mathbf{||h-h'||+||t-t'||}$,$S_{a_2}=\mathbf{||h-h'||+||r-r'||+||t-t'||}$即转换一方的坐标轴使两个对齐
• 转换向量：$S_{a_3}=\mathbf{||h+v^e_{ij}-h'||+||r+v^r_{ij}-r'||+||t+v^e_{ij}-r'||}$
• 线性转换：$S_{a_4}=\mathbf{||M^e_{ij}h-h'||+||M^e_{ij}t-t'||}$,$S_{a_5}=\mathbf{||M^e_{ij}h-h'||+||M^r_{ij}r-r'||+||M^e_{ij}t-t'||}$

其中$S_{a_3}-S_{a_5}$可逆，这也就对应模型的5种变体

整体损失函数$J=S_K+\alpha S_A$

利用随机梯度下降优化，在每一个epoch中，分别在不同的组优化$\theta\leftarrow\theta-\lambda\nabla_\theta S_K$和$\theta\leftarrow\theta-\lambda\nabla_\theta\alpha S_A$

依然应用二范数趋近于1来防止训练过程中通过缩小嵌入向量的方式来最小化损失函数

项目地址：https://github.com/muhaochen/MTransE

4. Cross-lingual Entity Alignment via Joint Attribute-Preserving Embedding

结构嵌入(TransE)只约束学习到的表示在每一个关系三元组内部兼容，导致由于关系三元组的稀疏(某些实体只分布在一个关系三元组中)，某些实体的分布是无序的。为了缓解这个问题，本文引入属性三元组帮助实体嵌入，因为可能对齐的实体常常有高度相似的属性值。使用属性值和范围类型，忽略具体的属性值。通过属性嵌入获取跨语种和单语种属性的关系，并计算基于属性嵌入的实体相似度，结合结构嵌入，通过聚类有高度属性联系的实体增强表示。

对于三元组$tr=(h,r,t),f(tr)=||\mathbf{h+r-t}||^2_2,tr'$为破坏后的三元组，即替换头或尾实体为随机实体。

结构嵌入损失函数(TransE)：最小化$O_{SE}=\sum\limits_{tr\in T}\sum\limits_{tr'\in T'_{tr}}(f(tr)-\alpha f(tr')),\alpha\in[0,1]$

种子实体共享相同嵌入，作为训练时链接两个KB的桥。具有相同头尾实体的可能是同一关系；具有相同头和关系的可能是同一尾

属性嵌入目标函数：最小化$O_{AE}=-\sum\limits_{(a,c)\in H}\omega_{a,c}\cdot logp(c|a)$，其中$logp(c|a)=log\sigma \mathbf{(a\cdot c)}+\sum\limits_{a,c'\in H'_a}log\sigma(-\mathbf{a\cdot c}),\sigma(x)=\frac{1}{1+e^{-x}}$

属性嵌入利用了skip-gram模型，利用属性预测相关属性。属性相关指两个属性在同一实体、对应种子实体。如果有相同类型，则相关性更强($\omega=1,2$)。$H_a'$是根据负对数基生成的错误对，假设都是错误的

实体相似度计算：实体利用正规化的属性嵌入表示$\mathbf e=[\sum\limits_{a\in A_e}\mathbf a]_1$

利用余弦距离表示实体相似度$sim(\mathbf{e,e'})=\mathbf{e\cdot e'}$，可以利用实体嵌入向量组成矩阵计算相似度矩阵$S^{i,j}=E_{AE}^{(i)}E_{AE}^{(j)T}$

利用相似度的平均值$\tau$,$S_{i,j}>\tau\rightarrow S_{i,j}=1,else\ S_{i,j}=0$

联合嵌入目标函数$O_{joint}=O_{SE}+\delta O_{S}$

其中$O_{S}=||E_{SE}^{(1)}-S^{(1,2)}E^{(2)}_{SE}||^2_F+\beta(||E_{SE}^{(1)}-S^{(1)}E^{(1)}_{SE}||^2_F+||E_{SE}^{(2)}-S^{(2)}E^{(2)}_{SE}||^2_F)$

训练时利用AdaGrad优化，并且可以分别优化$O_{SE}$和$\delta O_S$

训练结束后计算$\mathbf D=\mathbf E^{(1)}_{SE}\mathbf E^{(2)T}_{SE}$，将相似度降序排列，前几个作为对齐结果

项目地址：https://github.com/nju-websoft/JAPE

5. Iterative Entity Alignment via Joint Knowledge Embeddings

使用经典TransE: $K_T=\sum\limits_{T\in \{T_1,T_2\}}\sum\limits_{(h,r,t)\in T}L(h,r,t)$

$L(h,r,t)=\sum\limits_{(h',r',t')\in T^-}[\gamma+E(h,r,t)-E(h',r',t')]_+$

同时采用PTransE的策略，定义关系路径集$P(h,t)=\{p|\forall e\in E,r_1,r_2\in R,(h,r_1,e),(e,r_2,t)\in T,p=r_1\circ r_2\}$，如果一个关系路径和关系作用相同，$p\in P(h,t),(h,r,t)\in T$，定义路径嵌入$\mathbf{p\simeq r}$，$E(p,r)=||\mathbf{p-r}||=||\mathbf{p-(t-h)}||=E(h,p,t)$

评分函数$K_P=K_T+\sum\limits_{T\in \{T_1,T_2\}}\sum\limits_{(h,r,t)\in T}[\frac 1 Z\sum\limits_{p\in P(h,t)}R(p|h,t)L(p,r)],Z=\sum\limits_{p\in P(h,t)}R(p|h,t),R(p|h,t)$指在给定$(h,t)$时$p$的可靠性

$L(p,r)=\sum\limits_{(h,r',t)\in T^-}[\gamma+E(p,r)-E(p,r')]_+$

Modeling Relation Paths for Representation Learning of Knowledge Bases

利用路径资源约束算法表示路径的可靠性：h中有一定资源，通过p流向t，通过测量流向t的资源量反映p的可靠性

对于路径$S_0\rightarrow^{r_1}S_1\rightarrow^{r_2}\rightarrow^{r_3}...\rightarrow^{r_l}S_l$，$\forall\ entity\ m\in S_i,S_{i-1}(\cdot,m)$是

$m$通过$r_i$的直接前置，$S_{i}(n,\cdot)$是$S_{i-1}$中任意$n$通过$r_i$的直接后置，$R_p(n)$是从实体$n$获取到的资源

定义流向$m$的资源为$R_p(m)=\sum\limits_{n\in S_{i-1}(\cdot,m)}\frac{1}{|S_i(n,\cdot)|}R_p(n)$

$R_p(h)=1,R_p(h,t)=R_p(t)$

联合嵌入采用类似MTransE中的$S_{a_3},S_{a_4}$，即

• 转换模型：$E(e_1,e_2)=||\mathbf{e}_1+\mathbf{r}^{(E_1\rightarrow E_2)}-\mathbf{e}_2||$
• 线性变换模型：$E(e_1,e_2)=||\mathbf{M}^{(E_1\rightarrow E_2)}\mathbf{e}_1-\mathbf{e}_2||$，$\mathbb{L}$作为种子
• 前两种方法的分数函数为$J_{T/L}=\sum\limits_{(e_1,e_2)\in \mathbb{L}}\alpha E(e_1,e_2)$
• 参数共享模型：$e_1\equiv e_2,(e_1,e_2)\in\mathbb{L},J_P=0$

迭代训练：让新对齐的实体作为新种子添加，分为硬对齐($\mathbf e_1,\mathbf e_2\leftarrow\frac 1 2(\mathbf{e}_1+\mathbf{e}_2)$)和软对齐(减少误差传播的影响)：

赋予每一对齐的实体一个可靠性得分$R(e_1,e_2)=sigmod(k(\theta-E(e_1,e_2)))$

$\mathbb{M}$是不断添加新种子的集合

则得分函数$I_S=\sum\limits_{(e_1,e_2)\in\mathbb{M}}R(e_1,e_2)(H_{(e_1,e_2)}+H_{(e_2,e_1)})$

$H_{(e_1,e_2)}=\sum\limits_{(e_1,r,t)}U(e_2,r,t)+\sum\limits_{(h,r,e_1)}U(h,r,e_2)$

TransE中$U(h,r,t)=L(h,r,t)$，PTransE中$U(h,r,t)=L(h,r,t)+\frac 1 Z\sum\limits_{p\in P(h,t)}R(p|h,t)L(p,r)$

使用随机梯度下降训练，在软对齐中限制新增种子数量

6. Bootstrapping Entity Alignment with Knowledge Graph Embedding

$x,y$是待对齐的实体，对于$\tau=(h,r,t),f(\tau)=||\mathbf{h+r-t}||$

损失函数：$O_e=\sum\limits_{\tau\in T^+}[f(\tau)-\gamma_1]_++\mu\sum\limits_{\tau'\in T^-}[\gamma_2-f(\tau')]_+$。绝对小的嵌入可以防止空间中嵌入漂移的问题

由于$f(\tau')- f(\tau)\gt\gamma_2-\gamma_1$，所以也是一个margin-based，即可以控制$\gamma_1$和$\gamma_2$的值确定训练结果

Learning knowledge embeddings by combining limit-based scoring loss

负采样策略：如果随机替换则对于一些本来就相差很远的三元组来说，对于整体训练时没有帮助的。所以替换相近的三元组。

给定一个要替换的$x$，在嵌入空间中选择最相似的$s=\lceil(1-\epsilon)N\rceil,\epsilon\in[0,1)$个候选，利用余弦距离确定和$x$的相似度

在三元组中交换对齐的实体，来校准两个KG中的实体嵌入

$T^s_{(x,y)}=\{(y,r,t)|(x,r,t)\in T_1^+\}\cup\{(h,r,y)|(h,r,x)\in T_1^+\}\cup\{(x,r,t)|(y,r,t)\in T_2^+\}\cup\{(h,r,x)|(h,r,y)\in T_2^+\}$

这样就可以得到一个完整的$T^+=T_1^+\cup T_2^+\cup T^s$，然后负采样得到$T^-$

采用了Bootstraping策略，并且有编辑策略

在第$t$轮迭代解决如下优化问题，$max\sum\limits_{x\in X'}\sum\limits_{y\in Y'_x}\pi(y|x;\Theta^{(t)})\cdot\psi^{(t)}(x,y),\pi(y|x;\Theta)=\sigma(sim(\mathbf{x,y})),\Theta$是嵌入，$\sum\limits_{x'\in X'}\psi^{(t)}(x',y)\le1,\sum\limits_{y'\in Y'_x}\psi^{(t)}(x,y')\le 1,Y'_x=\{y|y\in Y'\ and\ \pi(y|x;\Theta^{(t)})\gt\gamma_3\},\gamma_3$是判定两个实体是否对齐的阈值

如果在$t$轮$x$标签是$y$则$\psi^{(t)}(x,y)=1$，否则为$0$。这是指标函数。在第$t$轮使用新对齐的实体对引导下一步对齐

为了提升对齐准确率，减少错误率，基于一对一对齐约束，提出错误修复方法

$\Delta^{(t)}_{(x,y,y')}=\pi(y|x;\Theta^{(t)})-\pi(y'|x;\Theta^{(t)})$

如果$\Delta>0$则说明有$y$比$y'$更适合和$x$对齐

$\phi_x$用于描述$x$的概率分布，即x获得所有标记的可能性

$\phi_x(\hat y)=\begin{cases}\mathbf 1,x\ is\ labeled\ as\ \hat y\\\frac 1 {|Y'|},x\ is\ unlabeled\end{cases}$

嵌入的目标函数$O_a=-\sum\limits_{x\in X}\sum\limits_{y\in Y}\phi_x(y)log\pi(y|x;\Theta)$

全局目标函数$O=O_e+\mu_2\cdot O_a$

利用AdaGrad随机梯度下降优化，嵌入的二范数约束为1

项目地址：https://github.com/nju-websoft/BootEA

7. Co-training Embeddings of Knowledge Graphs and Entity Descriptions for Cross-lingual Entity Alignment

同时采用了实体嵌入和实体描述来对齐实体，先使用实体嵌入找到对齐的实体，再使用实体描述找到另一部分对齐的实体

ILL：语言间链接

实体嵌入模型采用经典TransE，$S_k=\sum\limits_{L\in\{L_i,L_j\}}\sum\limits_{(h,r,t)\in G_L\wedge(\hat h,r,\hat t)\notin G_L}[f_r(h,t)-f_r(\hat h,\hat t)+\gamma]_+$

实体对齐模型采用线性转换$S_A=\sum\limits_{(e,e')\in I(L_i,L_j)}||\mathbf M_{ij}\mathbf e-\mathbf e'||_2$

实体描述采用注意力门控循环单元

$A(a_{ij})\odot B(b_{ij})=C(c_{ij})$是Hadamard product，$c_{ij}=a_{ij}\times b_{ij}$

《Deep Learning: Adaptive Computation and Machine Learning series》

https://zhuanlan.zhihu.com/p/106276295 ：重置门接近于0时，隐藏层被迫忽略之前的状态，仅用当前输入进行复位，有效地使隐藏状态丢弃将来发现的任何不相关信息；更新门控制将要有多少信息从前一个隐藏状态传递到当前隐藏状态，有助于记住长期信息

An Empirical Exploration of Recurrent Network Architectures

$z_t$是更新门，$g_t$是重置门，$s_t$是状态，$\tilde{s}_t$是对于$x_t$的候选状态

$s_t=\tilde s_t\odot z_t+(1-z_t)\odot s_{t-1}$

$M_z,N_z$是权重矩阵，$b_z$是偏差矩阵

$z_t=\sigma(M_z x_t+N_zs_{t-1}+b_z)$

$M_s,N_s$是权重矩阵，$b_s$是偏差矩阵

$\tilde{s}_t=tanh(M_sx_t+g_t\odot (N_ss_{t-1})+b_s)$

$g_t=\sigma(M_gx_t+N_gs_{t-1}+b_g)$

通过自注意力机制得到相同实体多语种描述中共享的部分

$u_t=tanh(M_as_t+b_a)$

$a_t=\frac{exp(u^Tx_t)}{\sum\limits_{x_i\in X}exp(u^T_ix_i)}$

$v_t=|X|a_tu_t$

$u_t$是$s_t$的一个隐藏表示，归一化注意力$a_t$是通过softmax计算的，测量$x_t$在对$X$编码中的重要性，应用到$u_t$上获取自注意力输出$v_t$，利用$|X|$包含长度信息

多语言词嵌入：在多语种并行语料库和单语种语料库上训练Bilbowa，训练好词向量之后固定词向量，然后放入描述编码器进行编码

使用双层堆叠GRU进行编码，利用仿射层将输入平均化$d_e=tanh(M_d(\frac 1 {|d_e|}\sum\limits_{i=1}^{|d_e|}v_i^{(2)})+b_d)$和输出相同

$S_D=\sum\limits_{(e,e')\in \{L_i,L_j\}}-LL_1-LL_2=\sum\limits_{(e,e')\in \{L_i,L_j\}}-log(P(e|e'))-log(p(e'|e))$

$LL_1=log\sigma(d_e^Td_{e'})+\sum\limits_{k=1}^{|B_d|}E_{e_k\sim U(e_k\in E_{L_i})}[log\sigma(-d_{e_k}^Td_{e'})]$

$LL_2=log\sigma(d_e^Td_{e'})+\sum\limits_{k=1}^{|B_d|}E_{e_k\sim U(e_k\in E_{L_j})}[log\sigma(-d_{e}^Td_{e_k})]$

$B_d$是ILL采样，同时负采样另一语言的所有$e_k$，除了$e$

8. Non-translational Alignment for Multi-relational Networks

TODO: 不全

基于TransE的方法表示能力较差，无法解决三角关系的问题，本文提出基于统计的方法

对于$v_i$，在$r_s$关系下有目标实体$v_j$的概率

目标函数：

$\omega_{ij}$是边权重

最小化目标函数可以得到嵌入

对齐目标函数：

利用随机梯度下降训练模型

利用余弦距离确定是否对齐

9. LinkNBed: Multi-Graph Representation Learning with Entity Linkage

学习一系列聚合器用于提取多图中的实体和关系的上下文信息，并将信息嵌入到低维空间中。利用这些表示学习关系分数。

• 如果两个实体对齐，则它们的嵌入距离相近
• 如果两个实体对齐，则在一个三元组中替换彼此，得到三元组分数相似

原子层：如下学习嵌入：$v^*=f(W^**),*\in\{e^s,e^o,r,t\}$分别是头尾实体、关系、类型的嵌入,$v^*$是学习后的嵌入，$W^*$是嵌入矩阵，$*$是对应的one-hot码，$f$是非线性激活函数(relu)

属性是键值对，如下嵌入：$a=f(W^{key}a^{key}+W_{val}a_{val}),a_{key},a_{val}$是key的one-hot和value的特征向量

上下文层：通过聚合相关实体向量学习不同的上下文信息$c(z)=AGG(\{z',\forall z'\in C(z)\})$

• $c(z)$是聚合后的上下文信息表示，$z$是实体或关系
• $C(z)$是在$z$上下文中出现的部件，$z'$是这些部件的向量表示
• AGG是合并器，可能是Mean,Max,Pooling,LSTM
• 上下文可能有不同影响，因此利用自注意力机制$c(z)=AGG(q(z)*\{z',\forall z'\in C(z)\})$,$q(z)=\frac{exp(\theta_z)}{\sum\limits_{z'\in\{C(z)\}}exp(\theta_{z'})}$,$\theta_z's$是注意力参数
• 实体邻居上下文：$N_c(e)$也是矩阵，对于$t=(e^s,r,e^o)$,$N_c(e^s)$为和$e^s$邻近但是不是$e^o$的实体，使用随机游走获取$k$轮$l$长度范围内的邻居。利用Mean聚合器
• 实体属性上下文：$A_c(e)$，收集$e$的所有实体属性嵌入，利用Max聚合器
• 关系类型上下文：$T_c(r)$，给定一个关系$r$，目标是获取关系中实体类型的影响。通过Mean聚合$r$的类型

表示层：计算原子层和上下文层后，利用如下获取最终表示和关系

关系分数：$g(e^s,e^r,e^o)=\sigma(z^{r^T}\cdot (z^{e^s}\odot z^{e^o}))$,$\sigma$是非线性激活函数，$\odot$是逐元素乘积

模型参数空间为$\mathbf\Omega=\mathbf{\{\{W_i\}_{i=1}^5,W^E,W^R,W^{key},W^{val},W^{v},\Theta\}}$

关系学习损失：$L_{rel}=\sum\limits_{c=1}^Cmax(0,\gamma-g(e^s_p,r_p,e^o_p)+g'(e_c^s,r_p,e^o_p),e^s_c$表示破坏三元组，$g'$评估破坏三元组的分数，$$

连接度学习损失：$L_{lab}=\sum\limits_{z=1}^Zmax(0,\gamma-g(e^+_Y,r_X,e^o_X)+g'(e^-_Y,r_X,e^o_X)_z)$，知识图谱X中的三元组$(e_X^s,r_X,e_X^o)$，首先找到Y中相同的实体$e^+_Y$替换$e_X^s$计算$g$，然后从Y中寻找所有$e_X^s$的负标签集合$E^-_Y$，

联合优化以上两个损失函数，得到最终损失函数$L(\mathbf\Omega)=\sum\limits_{i=1}^N[b\cdot L_{rel}+(1-b)\cdot L_{lab}]+\lambda||\mathbf\Omega||^2_2$

使用Adam随机梯度下降训练

10. Cross-lingual Knowledge Graph Alignment via Graph Convolutional Networks

对齐的实体通常有相似属性并且具有相似邻居，GCN可以结合属性和邻居信息，利用GCN将实体映射到低维向量

结构和属性嵌入：$[H_s^{(l+1)};H_a^{(l+1)}]=\sigma(\hat D^{-\frac 1 2}\hat A\hat D^{-\frac 1 2}[H_s^{(l)}W_s^{(l)};H_a^{(l)}W_a^{(l)}])$

其中$W_*^{\#}$是第$\#$层权重矩阵，$\sigma=ReLU$，

利用双层GCN进行训练，每一个GCN处理一个KG并生成嵌入

由于KG中关系是有类型的，所以计算$a_{ij}\in A$

$fun(r)=\frac{\#her}{\#tr}$

$ifun(r)=\frac{\#ter}{\#tr}$

$\#her,ter,tr$分别是带有关系$r$的头实体、尾实体和三元组数量

$a_{ij}=\sum\limits_{<e_i,r,e_j>\in G}ifun(r)+\sum\limits_{<e_j,r,e_i>\in G}fun(r)+$

实体对其度使用如下计算$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}$,$d_s,d_a$是结构嵌入和属性嵌入的维度，$f$是一范数

使用随机梯度下降训练，损失函数

$L_s=\sum\limits_{(e,v)\in S}\sum\limits_{(e',v')\in S'_{(e,v)}}[f(h_s(e),h_s(v))+\gamma_s-f(h_s(e'),h_s(v'))]_+$

$L_s=\sum\limits_{(e,v)\in S}\sum\limits_{(e',v')\in S'_{(e,v)}}[f(h_a(e),h_a(v))+\gamma_a-f(h_a(e'),h_a(v'))]_+$

项目地址：https://github.com/1049451037/GCN-Align

Entity Alignment between Knowledge Graphs Using Attribute Embeddings

属性谓词对齐：属性谓词可能有命名转换和部分对齐，所以使用最后一部分的编辑距离进行对齐，阈值0.95

利用TransE学习结构嵌入$J_{SE}=\sum\limits_{t_r\in T_r}\sum\limits_{t_r'\in T_r'}max(0,\gamma+\alpha(f(t_r)-f(t_r')))$,$\alpha=\frac{count(r)} {|T|}$,$\alpha$用于控制从已经对齐的实体上学到更多，因为对齐的谓词比没对齐的谓词要多

属性字符嵌入：

$f_a$是组合函数，包括n-gram法 和LSTM法

联合嵌入损失函数

实体对齐：

同时利用属性增强规则，即

GCN-Align

对齐的实体通常有相似属性并且具有相似邻居，GCN可以结合属性和邻居信息，利用GCN将实体映射到低维向量

结构和属性嵌入：$[H_s^{(l+1)};H_a^{(l+1)}]=\sigma(\hat D^{-\frac 1 2}\hat A\hat D^{-\frac 1 2}[H_s^{(l)}W_s^{(l)};H_a^{(l)}W_a^{(l)}])$

其中$W_*^{\#}$是第$\#$层权重矩阵，$\sigma=ReLU$，

这里$\hat D^{-\frac 1 2}\hat A\hat D^{-\frac 1 2}$实际上计算了一个矩阵的对称归一化，$D^{0.5}$就是矩阵每一个元素都${}^{0.5}$

https://zhuanlan.zhihu.com/p/412337460

利用双层GCN进行训练，每一个GCN处理一个KG并生成嵌入

由于KG中关系是有类型的，所以计算$a_{ij}\in A$ 这个A就是上面的A，用于表示图的结构信息

$fun(r)=\frac{\#her}{\#tr}$

$ifun(r)=\frac{\#ter}{\#tr}$

$\#her,ter,tr$分别是带有关系$r$的头实体、尾实体和三元组数量

代码实现

def func(KG):
    head = {} # 头实体的数量
    cnt = {} # 关系的数量
    for tri in KG:
        if tri[1] not in cnt:
            cnt[tri[1]] = 1
            head[tri[1]] = set([tri[0]])
        else:
            cnt[tri[1]] += 1
            head[tri[1]].add(tri[0])
    r2f = {}
    for r in cnt:
        r2f[r] = len(head[r]) / cnt[r]
    return r2f


def ifunc(KG):
    tail = {} # 尾实体的数量
    cnt = {} # 关系的数量
    for tri in KG:
        if tri[1] not in cnt:
            cnt[tri[1]] = 1
            tail[tri[1]] = set([tri[2]])
        else:
            cnt[tri[1]] += 1
            tail[tri[1]].add(tri[2])
    r2if = {}
    for r in cnt:
        r2if[r] = len(tail[r]) / cnt[r]
    return r2if


def get_weighted_adj(e, KG):
    r2f = func(KG) # r->头实体比例
    r2if = ifunc(KG) # r->尾实体比例
    M = {}
    for tri in KG:
        if tri[0] == tri[2]:
            continue
        if (tri[0], tri[2]) not in M:
            M[(tri[0], tri[2])] = max(r2if[tri[1]], 0.3)
        else:
            M[(tri[0], tri[2])] += max(r2if[tri[1]], 0.3)
        if (tri[2], tri[0]) not in M:
            M[(tri[2], tri[0])] = max(r2f[tri[1]], 0.3)
        else:
            M[(tri[2], tri[0])] += max(r2f[tri[1]], 0.3)
    row = []
    col = []
    data = []
    for key in M:
        row.append(key[1])
        col.append(key[0])
        data.append(M[key])
    return sp.coo_matrix((data, (row, col)), shape=(e, e))

# ...
# 下面用于获取\hat A
adj + sp.eye(adj.shape[0])
# 然后进行一个正规化
def normalize_adj(adj):
    """Symmetrically normalize adjacency matrix."""
    adj = sp.coo_matrix(adj)
    rowsum = np.array(adj.sum(1)) # 每一行求和
    d_inv_sqrt = np.power(rowsum, -0.5).flatten() 
    d_inv_sqrt[np.isinf(d_inv_sqrt)] = 0.
    d_mat_inv_sqrt = sp.diags(d_inv_sqrt)
    return adj.dot(d_mat_inv_sqrt).transpose().dot(d_mat_inv_sqrt).tocoo()

$a_{ij}=\sum\limits_{<e_i,r,e_j>\in G}ifun(r)+\sum\limits_{<e_j,r,e_i>\in G}fun(r)+$

实体对其度使用如下计算$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}$,$d_s,d_a$是结构嵌入和属性嵌入的维度，$f$是一范数

使用随机梯度下降训练，损失函数

$L_s=\sum\limits_{(e,v)\in S}\sum\limits_{(e',v')\in S'_{(e,v)}}[f(h_s(e),h_s(v))+\gamma_s-f(h_s(e'),h_s(v'))]_+$

$L_s=\sum\limits_{(e,v)\in S}\sum\limits_{(e',v')\in S'_{(e,v)}}[f(h_a(e),h_a(v))+\gamma_a-f(h_a(e'),h_a(v'))]_+$

代码实现

def align_loss(outlayer, ILL, gamma, k):
    left = ILL[:, 0] # 源实体
    right = ILL[:, 1] # 目标实体
    t = len(ILL)
    left_x = tf.nn.embedding_lookup(outlayer, left) # 获取left中所有实体的嵌入
    right_x = tf.nn.embedding_lookup(outlayer, right) # 获取right中实体的所有嵌入
    A = tf.reduce_sum(tf.abs(left_x - right_x), 1) # L1-norm
    neg_left = get_placeholder_by_name("neg_left") # 获取负实体 #tf.placeholder(tf.int32, [t * k], "neg_left")
    neg_right = get_placeholder_by_name("neg_right") #tf.placeholder(tf.int32, [t * k], "neg_right")
    neg_l_x = tf.nn.embedding_lookup(outlayer, neg_left)
    neg_r_x = tf.nn.embedding_lookup(outlayer, neg_right)
    B = tf.reduce_sum(tf.abs(neg_l_x - neg_r_x), 1)
    C = - tf.reshape(B, [t, k])
    D = A + gamma
    L1 = tf.nn.relu(tf.add(C, tf.reshape(D, [t, 1]))) # 第一对的损失值
    neg_left = get_placeholder_by_name("neg2_left")# 选了第二对负实体 #tf.placeholder(tf.int32, [t * k], "neg2_left")
    neg_right = get_placeholder_by_name("neg2_right") #tf.placeholder(tf.int32, [t * k], "neg2_right")
    neg_l_x = tf.nn.embedding_lookup(outlayer, neg_left)
    neg_r_x = tf.nn.embedding_lookup(outlayer, neg_right)
    B = tf.reduce_sum(tf.abs(neg_l_x - neg_r_x), 1)
    C = - tf.reshape(B, [t, k])
    L2 = tf.nn.relu(tf.add(C, tf.reshape(D, [t, 1]))) # 第二对损失函数
    return (tf.reduce_sum(L1) + tf.reduce_sum(L2)) / (2.0 * k * t) # 归一化

项目地址：https://github.com/1049451037/GCN-Align

实际实现还加了Dropout层

源码中发现如果有多个support($\hat D^{-\frac 1 2}\hat A\hat D^{-\frac 1 2}$)会将这些support加起来，共同起作用

(A矩阵过于单薄了吧)

环境

conda create -n gcn-align python==3.6

conda install cudatoolkit==9 cudnn==7.3.1 scipy==1.1.0 networkx==2.2

pip install tensorflow-gpu==1.10.1

Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs

Google翻译有20%的错误，会导致初始嵌入问题

将$G_1$和$G_2$放在一起，点集$V^e=E_1\cup E_2$，边集$\epsilon^e=T_1\cup T_2$，由于种子实体并未联通，所以$G_1,G_2$没有联通

首先构造对偶关系图：给定原始图 Ge，其对偶关系图 Gr = (Vr, Er) 构造如下： 1) 对于 Ge 中的每一种关系 r，在 Vr 中都会有一个顶点 vr，因此 Vr = R1 ∪R2； 2) 如果两个关系 ri 和 rj 在 Ge 中共享相同的头或尾实体，那么我们在 Gr 中创建一条边 ur ij 连接 vr i 和 vr j

$u^r_{ij}$的权重$w^r_{ij}$表示两个关系$r_i,r_j$共享的实体有多相似

对偶关系图和原始图的节点表示通过GAT获取，可以更好的让两图交互。通过堆叠多个交互来让两个图互相提升

对偶注意力层：输入：$X^r\in\mathbb R^{m\times 2d}$，每一行是一个节点的表示，$N^r_i$是$v^r_i$的邻居索引集，$\alpha^r_{ij}$是对偶注意力，$\sigma^r$是ReLU，$\eta$是Leaky ReLU,$a^r$是一个2d全连接层，可以将$2d'$维的输入映射到常数，$c_i$是从之前的原始注意力层获取的关系$r_i$的关系表示,$\tilde\mathbf x^r$是点$v^r_i$的输出表示

在基于嵌入的框架中，关系表示无法直接提供，因此结合原始图中平均后的头和尾实体表示关系。当是第一层对偶关系层时，相关参数通过初始化获取

原始图GAT利用对偶关系表示计算节点嵌入。输入$X^e\in\mathbb R^{n\times d}$。对于实体$e_q$，$x^r_{qt}$是从实体$q$通过关系$r$到$t$中$r$的表示，$N^e_q$是邻居索引

初始嵌入使用词嵌入表示，将初始嵌入混合到输出中用于添加词嵌入信息

利用双层GCN捕捉更深远的邻居结构

并且GCN之前使用门控网络用于抑制噪声积累和保留有用的信息

对齐是使用距离

训练的损失函数如下，$\mathbb L$是种子，$\mathbb L'$是破坏的种子对。破坏种子对不是随机选，而是根据距离随机选k个最近的非对齐种子

项目地址：https://github.com/StephanieWyt/RDGCN

RAGA: Relation-aware Graph Attention Networks for Global Entity Alignment

包含4层，基础邻居合并层、关系感知的图注意力网络、端到端训练、全局对齐算法

基础邻居合并层，由门控图卷积神经网络构成，但是去掉了权重矩阵$W^{(l)}$

关系感知的图注意力网络

由于关系的分布比实体的分布更致密，关系表示应该有不同的信息量并且有不同的信息空间。对实体嵌入应用一个线性转换，然后利用注意力权重计算关系嵌入。利用连接的头实体和尾实体，和RDGCN不同，不忽略实体关系双连接，用于调整注意力权重

关系嵌入如下

上式表示的是关系k相对于头实体$h$的嵌入，相对于尾实体t的嵌入计算方法相同。最终的关系表示如下

关系感知的实体表示：根据经验，一个实体的邻居关系更能够精确表示自身，因此将近邻关系重新分组到实体表示中，特定的，对于实体$e_i$，计算外向嵌入(作为头实体)和内向嵌入(作为尾实体)

增强实体表示：在关系感知实体表示中，实体感知了一跳实体，为了加强2跳实体的影响，增加一层一般GAT来获取增强实体表示，考虑双向边并且不包含线性转换矩阵

因为$N_i$是邻居实体集合，邻居包含两跳的关系，所以这里就利用了两跳的关系

端到端训练

使用曼哈顿距离表示两个实体的相似度

损失函数如下，训练时随机采样k个最近的负样本。对于KG中的每一个三元组都认为是正样本

全局对齐算法：实体的局部对齐会导致多对一的问题并且降低性能并且带来歧义，使用微调相似度代替原来的相似度。使用DAA算法对齐(Collective Embedding-based Entity Alignment via Adaptive Features)

在第一轮中，每个源实体向它最喜欢的目标实体提出建议，然后目标实体与它目前最喜欢的源实体临时匹配，同样，该源实体与目标实体临时匹配

在随后的每一轮中，每个未匹配的源实体向它尚未提议的最优选的目标实体提出建议（无论目标实体是否已经匹配），然后每个目标实体如果当前不匹配则接受提议 或者如果它更喜欢新的提议者而不是它当前的匹配（在这种情况下，它拒绝它的临时匹配并且变得不匹配）。

环境

创建环境conda create -n raga

激活环境conda activate raga

安装torch conda install pytorch torchvision torchaudio pytorch-cuda=11.6 -c pytorch -c nvidia 目前网速较慢，需要提高网速可以下载对应文件之后搭建稳定的本地镜像源

然后编译安装apex，就很麻烦

首先安装cuda-nvprof，这个包提供cuda_profiler_api.h头文件，注意版本和conda list列出的cuda-toolkit版本相同

conda install -c "nvidia/label/cuda-11.6.2" cuda-nvprof

clone代码并编译，这里可以提前安装ninja提高编译速度

pip install packaging && git clone https://github.com/NVIDIA/apex.git && cd apex && pip install -v --disable-pip-version-check --no-cache-dir --global-option="--cpp_ext" --global-option="--cuda_ext" ./

安装另外两个包conda install pytorch-sparse -c pyg,pip install torch_geometric

导出环境 conda env export > RAGA_conda.yml

导入 conda env create -f RAGA_conda.yml

参考自：https://github.com/PaddlePaddle/Paddle/issues/45929

Multi-information embedding based entity alignment