2020.1.2更新
A Re-evaluation of Knowledge Graph Completion Methods
这篇文章评估了以下几个模型的真实表现，想知道各模型具体evaluation的可以看这篇文章。总结就是，目前看来最有意义的模型应该还是最早的ConvE。
另外ConvE在计算参数这一块有些问题，具体可以看
https://github.com/TimDettmers/ConvE/issues/57
同时ConvE还有一个正统的升级版本(填了future work的坑):
InteractE
至于为什么ConvE能在那么多模型中脱颖而出(像那么多模型声称ConvE有缺陷但是还比不上ConvE)，个人感觉ConvE的本质其实也是将嵌入向量映射到别的空间去表征他，而得益于卷积结构强大的特征提取能力，可以获得很好的参数利用率(parameter efficient)。
这个也可以看看:
https://github.com/irokin/Experiments-Results-for-Link-Prediction
本文旨在比较知识库补全(KBC)最近两年使用到卷积的几个模型。
对于实验结果，由于各家都是在自己的文章里吊打别人，所以下面给出paperswithcode的SOTA榜单作为参考:
FB15K-237 Link Prediction
WN18RR Link Prediction
Introduction
ConvE
AAAI 2018
Convolutional 2D Knowledge Graph Embeddings
code
作者认为链路预测(link prediction)之前的研究工作都聚焦于浅层快速的模型使其可以应用于大型知识图谱，但是性能会受制于浅层的架构。这篇文章中作者提出了一个多层卷积模型ConvE用于链路预测。这篇文章/模型主要的亮点有:
1.提出的ConvE除了实验结果好，参数利用率高（相同表现下参数是DistMult的八分之一，R-GCN的十七分之一），使用了1-N score使训练和测试加快了三百倍，并且在复杂的图结构(含有高入度节点)上效果很好。
2.NLP中使用的CNN都是Con1D(比如Text-CNN)，一维卷积以句子为单位来卷积。本文构思了ConV2D的实现方法，即三元组的得分函数是由二维卷积获得。
3.提出(并不是第一个发现)一些数据集比如WN18和FB15k有测试集泄漏(test set leakage)的问题，即测试集中的三元组可以通过翻转训练集中的三元组得到，比如测试集中有(s,hyponym,o) 而训练集中有(o,hypernym,s)。这个问题的存在导致一些很简单的模型就可以在某些数据集上实现SOTA。作者构造了一个简单的inverse model来衡量这个问题的严重性，还清洗了部分数据集来解决这个问题。
ConvKB
NAACL-HLT 2018
A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network
code
本文也是用卷积去处理三元组，与ConvE不同的是ConvKB中三元组被作为三列的矩阵输入每列为三元组元素的嵌入同时卷积为Conv1D。作者认为ConvE只考虑了局部不同维度的关系没有考虑全局相同维度的关系，所以ConvE无视了transitional特性(我的理解就是ConvE中只对头实体和关系卷积，而ConvKB对三个元素都进行了卷积并且由于三元组表现为三列所以卷积时三列相同维度被一起提取特征)。这篇文章/模型主要的亮点是在WN18RR和FB15K-237上获得了SOTA的MRR和Hits@10(然鹅paperswithcode的榜单中FB15K-237并没有录入,WN18RR排名第九)。
CapsE
NAACL-HIT 2019
A Capsule Network-based Embedding Model for Knowledge Graph Completion and Search Personalization
code
本文的作者和ConvKB是一个人，Dai Quoc Nguyen，有一个合作者叫Dat Quoc Nguyen之前差点把这两人当作一个人了署名缩写都一样。这两人在KBC领域很活跃，不知道是不是亲兄弟。
模型在之前ConvKB的基础上，卷积提取特征图后加入胶囊网络(关于胶囊网络详见知乎专栏)。这篇文章/模型主要的亮点是
1.第一篇在KBC任务中加入胶囊网络的模型.
2.在WN18RR上获得了SOTA的MR，FB15k-237上获得了SOTA的MRR和Hits@10(aperswithcode榜单没有录入)。
3.文章也在搜索个性化(search personalization)的数据集中做了尝试。搜索个性化就是相同的搜索关键词，对不同的用户返回不同的结果，抽象为三元组(submitted query,user profile,returned document) ，这里就不深入展开了。
4.实验最后全面对比了ConvKB和CapsE，CapsE对many-to-many类型的三元组建模能力很强。
这里注意到WN18RR中存在最多的关系是hypernym，ConvE中提到的test leakage 问题举例也就是hypernym和hyponym的转置问题。
Conv-TransE(SACN)
AAAI 2019
End-to-end Structure-Aware Convolutional Networks for Knowledge BaseCompletion
code
本文提出了模型SACN( Structure Aware Convolutional Network)。这篇文章/模型主要的亮点是考虑了图的结构信息，SACN由编码器WGCN(weighted graph convolutional network)和解码器Conv-TransE组成，前者获得图的结构信息，后者使得模型可以完成Link Prediction。模型在WN18RR和FB15K-237上获得了SOTA的HITS@1, HITS@3 and HITS@10，结果paperswithcode的榜单中没有记录。
因为是几个模型的横向比较，所以这里只解释Conv-TransE的结构，Conv-TransE是ConvE的改进版，decoder没有采用ConvKB是因为ConvKB这种直接输入完整三元组嵌入进行卷积的模式不适合SACN端到端模型。
Scoring Function
ConvE
e，r为实体和关系的嵌入，ne为训练集中的实体数量nr为关系数量，对应的嵌入维度为k和k'(一般k=k'，博客之后也默认k=k')。在ConvE的scoring function中，f是非线性激活函数文章中用的是relu+BN，vec()表示将张量拉平为向量，表示用卷积核进行卷积操作。[ ]操作符为对嵌入e和r进行变形拼接(2D reshaping)最后得到一个矩阵。矩阵的维度为kw x kh ，其中kwkh=2k(注意原文中是k=kwkh，这里应该是原文有误，两个向量变形拼接为矩阵后元素个数不变)。输出越大表明这个三元组越可靠。
可以注意到空间复杂度上ConvE和DistMult是一样的，即ConvE可以用更少的嵌入维度获得和DistMult一样的效果。
ConvKB
可以和ConvE的图对应着看，对于输入的(h,r,t)三元组，将其转换为三元组元素嵌入vh,vr,vt在列方向上拼接组成的矩阵，用1x3的卷积核进行卷积(没错是Conv1D)。之后将卷积后得到的特征图(因为是Conv1D所以是向量)拼接起来，和权重向量w进行内积。输出越小表明这个三元组越可靠(注意ConvKB的损失函数里没有负号)。
CapsE
在ConvKB卷积的步骤之后，添加胶囊网络。最后输出的是d维向量e(d是第二层胶囊网络中神经元数量)，这个向量的模越大表明这个三元组越可靠。
Conv-TransE(SACN)
M(es,er)，C是通道个数k是嵌入维度，M(es,er)是由卷积过后的C个k维特征图Mc(es,er)堆叠起来，通道c的单张特征图Mc(es,er)=[mc(es,er,0),...,mc(es,er,k-1)]，上图是向量中第n位元素mc(es,er,n)的计算公式。看起来花里胡哨的，其实就是卷积操作:wc是通道c，2xk卷积核的参数，()里的数代表矩阵wc的第几位和嵌入向量的第几位相乘。将拉平后的向量投影至k维。f()非线性激活函数文章中没提采用什么，估计和ConvE配置一样。
Conv-TransE和ConvE唯一的区别是Conv-TransE输入的嵌入向量没有reshape，下文中看模型架构会更很清晰。
这里卷积时会zero-padding。
Model
ConvE
所有实体与关系的嵌入可以看作为两个矩阵，实体嵌入，关系嵌入
，
为图谱中实体的数量(注意不等于ne+nr，因为有些实体同时是头实体和尾实体)，
为图谱中关系的数量。嵌入矩阵的每一行即代表一个实体或者一个关系的嵌入。
按图中从左到右我们将步骤分为六步:
1.对于输入三元组(es，r，eo)，我们首先查询嵌入矩阵获得es和er的嵌入向量(各k维，图中的话是4维)。
2.变形拼接(2D reshaping)得到kw x kh的矩阵(图中是4x2)。作者在这层加入了dropout(0.2)，即有两个元素置为0(dropout并不会减少维度只是置0，这里顺便贴以下dropout实现keras的源码:
sample=np.random.binomial(n=1,p=retain_prob,size=x.shape
x *=sample
x /= retain_prob
)
3.卷积后获得张量，c是通道数，即卷积核个数。同样的dropout0.2这样是直接将两个通道置0。按照图中c=8，m=3，n=3(这不是卷积核的大小而是卷积后获得张量的大小，卷积核大小文中实验使用的是3x3)。
4.拉平后vec()的行向量。随后使用全连接映射到k维向量(本文实验采用的k=200，图里画的是列向量但是按照文章里的维度标识应该得到的是1xk的行向量)，dropout0.3两个元素置0。
5.得到的hidden layer k维向量和目标尾实体eo做内积并取对数，输出越大说明三元组(es，r，eo)成立的可能性越大。因为卷积操作占了75%以上的计算时间，因此要想加快计算必须要尽可能减少卷积操作的次数，所以这里我们一次性让hidden layer和图谱中所有实体做内积(图中12个)，这就是1-N score，区别于只和一个做内积的1-1 score。这样得到的便是维的向量。
6.sigmoid后输出分布。注意虽然输出的分布包含了所有实体，但是输入仍是(es，r)头实体和关系2个k维向量。
ConvKB
图中元素嵌入维度k=4，作者认为这样的卷积不但考虑到了全局同一维度的特征，更是transitional特性的体现(可能嵌入向量间相同维度运算就是transitional特性?)。
值得注意的是，图中有3个卷积核，如果我们只保留一个卷积核且设置为[1,1,-1]，那ConvKB就会变成TransE (h+r-t)，所以作者认为可以视为对TransE的传承。
CapsE
图中嵌入维度k=4，卷积核个数N=5，第二层胶囊网络中神经元数量d=2(第一层胶囊网络中神经元数量和卷积核个数一致)。
和下面的算法流程对应着看:
卷积后的得到的特征图矩阵对应流程中的u1，...uk(k为嵌入维度，卷积后特征图的维度也为k)。对胶囊网络感兴趣的也可以看知乎专栏。
Conv-TransE
我们把重点放在Conv-TransE接收到输入实体嵌入es和关系嵌入er开始，其实和ConvE是一样的这里从左到右算作三步:
1我们从WGCN层获得所有实体和关系的嵌入矩阵，随后查询矩阵获得es和er的嵌入向量(各k维，图中的话是4维)。
2.上下堆叠后进行卷积(也就是这里和ConvE不一样，没有reshape，同时Conv-TransE中没有dropout)。按照图中卷积核为2x3，3通道。得到的三个特征图叠起来便是Scoring Function中的M(es,er)，矩阵维度3x4。
3.将上一步中的矩阵拉直，随后做全连接到嵌入维度，之后和ConvE中1-N scoring一样和所有实体嵌入向量做内积，随后取对数sigmoid函数后输出分布。输出越大说明三元组(es，r，eo)成立的可能性越大。
Loss Function
ConvE
训练时令，训练时需要最小化的损失函数如下:
ti是标签，即(es，r，eo)在训练集中存在为1，不存在为0。1-N时为维。文章之后提到试过1-0.1N收敛太慢，默认的话N=。这里应该是直接全部反向传播没有做负采样。
ConvKB
f()是scoring function，加入了对权重向量w的L2正则化。同时负样本采样是采用了Bernoulli trick(TransH中提出的一种负例采样技巧旨在减少产生false negative，当然即使产生了也会被filttered详见TransE 4.2节)。
CapsE
负样本采样和ConvKB一样是采用了Bernoulli trick(TransH中提出的一种负例采样技巧旨在减少产生false negative
Conv-TransE
文章中没有提，只提到了同样。猜测损失函数和ConvE应该是一致的。代码中确认一致bceloss。
Experiments
Datasets and test leakage
WN18是WordNet的子集有18个关系和40,943个实体。FB15K是Freebase的子集有1,345个关系和14,951个实体。然而在这两个数据集中94%以及81%的三元组都有转置关系，比如测试集中的(feline, hyponym, cat)和训练集中的 (cat, hypernym, feline) ，这样使得任何模型都可以在这些数据集上获得很好的表现。
WN18RR包括11个关系和40,943个实体，去除了7个WN18中存在的转置关系以及对应的三元组。同样的还有FB15K-237，保留了237个关系14,541个实体。
因为上面两个数据集包含的都是(实体,关系,实体)类型的三元组，没有(实体,属性,值)这类的三元组，所以Conv-TransE文中从FB24K中抽出了78,334个属性相关三元组包含203种属性，组成了FB15K-237-Attr数据集。该数据集在Conv-TransE的实验中并入了FB15K-237的训练集，使得SACN中WGCN学习到了更好的实体及关系嵌入最终在FB15K-237的训练集上获得了更好的结果(其实都是0.01的提升感觉有一些自圆其说，下面看图就知道了)。
这里再贴一下paperswithcode的SOTA榜单:
FB15K-237 Link Prediction
WN18RR Link Prediction
同时这几篇文章中的结果都是在“Filtered” 的数据集上，意为在处理过了生成的负例(详见TransE 4.2节)。
ConvE
本文中作者构建了一个只识别转置关系的模型Inverse Model，训练时提取出三元组满足转置的所有关系r，测试时给到(s,r1,?)时模型寻找测试集外是否有三元组(o,r2,s)并且将所有可能的o作为预测结果(大致是这样，感觉文章也没有讲的特别清楚)。
使用Adam优化，超参数设置为嵌入维度k=200，batch size 128，学习率0.001，label smoothing0.1(label smoothing起到抑制过拟合的效果,修改损失函数中的ti使其平滑不再是0或1)，卷积通道数文章中没有给出，代码中为32通道。
图中可以看到在新的数据集上实验结果明显低了很多，Inverse Model尤其明显，说明了WN18和FB15k的test leakage 的问题非常严重。同时可以看到ConvE在FB上的表现更好，因为FB图谱更复杂节点有更大的入度，而深层模型更适合对复杂图谱建模。
ConvKB
Adam优化，超参数设置为嵌入维度k=100，batch size 256，学习率5e^-6(约等于0.01)，卷积通道数50。
作者文中还吐槽了ConvE部分表现没有TransE好，并且ConvKB优于ConvE是因为应用了transitional特性(然鹅FB15K-237结果并没有被paperswithcode记录,WN18RR排名第九)。
CapsE
Adam优化，超参数设置为嵌入维度k=100，batch size 128，第二层胶囊网络神经元个数d=10，routing algorithm 迭代次数m =1，FB15K-237 时卷积核个数N=50，学习率1e-4(约等于0.02)，WN18RR 时卷积核个数N=400，学习率1e−5(约等于0.007) 。
Conv-TransE
Adam优化，超参数设置为嵌入维度k=200， 学习率0.003，FB15K-237 时100个卷积核，WN18RR 时200个卷积核。
使用FB15K-237-Attr的提升都是0.01微乎其微。(加入FB15K-237-Attr的目的是为了让编码器WGCN学习到更多的节点信息及图结构)
可以看到仅仅使用Conv-TransE就可以获得不错的结果。作者还实验了加入ConvE+FB15K-237-Attr，实验结果并没有获得提升(FB15K-237-Attr本来就是喂给WGCN的)。
