今天给大家介绍收录在NIPS2019的文章“Multi-relational Poincaré Graph Embeddings”，该文章由爱丁堡大学信息学院和剑桥三星AI中心合作完成。这篇文章提出了一种多关系庞加莱模型（MuRp），该模型将多关系图数据嵌入到双曲空间庞加莱球中，使得模型在低维链路预测的效果上，明显优于欧几里得空间中相关模型和现有的其他模型。
1
研究背景
然而，在分层多关系图数据结构中，双曲空间嵌入方法性能却不如欧几里得模型。因为在双曲空间中很难找到一种方式来表示跨关系共享的实体(节点)，使得它们在不同的关系下形成不同的层次。目前，许多建模多关系数据的方法，是依赖于内积作为相似性度量，但是在双曲空间中没有与这些模型对应的欧几里德内积转换。即使有些使用欧几里德距离来度量相似性的方法可以转换到双曲空间，但它们在预测性能方面不如双线性模型。
结合以上一系列问题，该文章提出了将分层多关系数据嵌入双曲几何的庞加莱球中（MuRP）的方法。MuRP通过莫比乌斯矩阵向量乘法和莫比乌斯加法，来学习转换实体嵌入的特定关系参数。知识图谱是一个典型的分层多关系数据结构，将其嵌入到双曲空间中可能会有较明显的改进。因此该文章重点研究在双曲空间中嵌入多关系知识图谱数据，并进行链路预测。经过和多关系欧几里得模型（MuRE）的一系列比对分析表明，维度越低，MuRP模型链路预测的效果比MuRE越好。
2
多关系庞加莱嵌入
2.1 双曲几何庞加莱球
要想把双曲线模型与庞加莱球结合，首先应先了解一下庞加莱球的模型。定义一个半径为1/√c(c>0)的d维流形庞加莱球(Bcd,gB)，其中Bcd={x∈Rd:c‖x‖2<1},gB=(λxc)2gE,λxc=2/(1-c‖x‖2)，x，y∈Bcd。x，y两点之间的最短路径为式1所示：
其中‖∙‖表示欧几里得范数，⊕c表示莫比乌斯加法。而莫比乌斯加法运算如式2所示：
其中表示欧几里得内积。莫比乌斯矩阵向量乘法运算如式3所示：
其中x通过对数映射到切线空间0中，x∈Bcd,M∈Rd*k，0∈Bcd。
图1 (a)庞加莱球中点对之间的最短路径。(b)该模型预测三元组真假。(c)每个嵌入的实体影响范围
2.2 多关系图嵌入得分函数
了解了双曲几何庞加莱球之后，得分函数也是模型不可或缺的部分。一组实体可以在不同的关系下形成不同的层次结构，而理想的嵌入模型应该同时捕获所有层次结构。双线性模型使用欧几里得内积来度量主体实体嵌入和客体实体嵌入之间的相似性。但是，在双曲空间中并不存在明确的欧几里得内积对应。同时，研究者们发现，在word2vec词嵌入中出现类比线性结构。而类比与多关系图中的关系有很多相似之处，因此该研究使用以前的启发式转换方法对关系建模是可行的。多关系图嵌入的得分函数如式4所示：
其中，d是距离函数d:ℇ×R×ℇ→R ；es、eo表示主客体实体嵌入es，eo∈Rd；R∈Rd*d是对角关系矩阵；bs、bo分别表示其标量偏差bs，bo∈R。
知道了多关系图嵌入得分函数，将得分函数与双曲几何庞加莱球相结合，从而应用到MuRP模型中，需要做一个适当的变换，变换后的MuRP模型得分函数如式5所示：
其中hs，ho∈Bcd分别表示主客体实体es和eo的双曲嵌入，rh∈Bcd是关系r的双曲平移向量，hs(r)∈Bcd通过Möbius矩阵-向量乘法得到，ho(r)∈Bcd由Möbius加法得到，R是对角关系矩阵。MuRP的参数数随实体和关系的数目线性增加，从而具有较大的知识图谱可伸缩性。为了获得预测的事实为真的概率，该研究将logistic sigmoid即σ(ΦMuRP(es，r，eo))应用在得分函数上。
2.3 训练与优化
该研究使用标准的数据扩充技术，为每个三元组(es，r，eo)添加逆关系(eo，r−1，es)，同时为每个真三元组(es，r，eo)生成k个负样本，其然后从所有实体集合ℇ中随机选择破坏客体(es，r，eo’)或主体(eo，r−1，es’)实体。这两个模型都用来训练最小化伯努利负对数似然损失，计算方法如式6所示：
其中，p是预测概率，y是指示样本是正还是负的二进制标签，N是训练样本的数量。
为了较好的看出实验模型的效果，该研究同时用多关系欧几里得模型（MuRE）与本模型做了一个对比。
实验时，该研究用随机梯度下降（SGD）和黎曼随机梯度下降（RSGD）分别对欧几里得模型和双曲线模型进行了优化。在这里作者为了计算黎曼梯度∇RL，将欧几里得梯度∇EL乘以庞加莱度量张量的逆，即∇RL=1/(λθc)2∇EL。同时使用expθc将梯度映射到庞加莱球上的对应测地线，从而更新黎曼梯度，即θ←expθc(−η∇RL)，其中η表示学习率。
3
实验
3.1 数据集
文章首先使用标准WN18RR和FB15k-237数据集测试庞加莱和欧几里得模型在知识图谱链接预测任务中的性能。其中FB15k-237是Freebase的子集，Freebase是真实世界事实的集合。WN18RR是WordNet的子集，WordNet是词之间关系的分层集合。该研究从验证和测试集中删除许多关系的逆项，以使数据集更具挑战性。WN18RR是分层的，而FB15k-237不是分层的，所以该研究还在包含75492个实体和200个关系的NELL-995数据集上进行了对比实验，该数据集包含22%的分层数据，以观察文章提出的MuRP模型在分层数据集上的性能。文章使用MRR和hits@k，k∈｛1，3，10｝来评估实验结果。
3.2 实验参数设置
文章使用PyTorch实现MuRP和MuRE这两个模型。实验发现，这两个模型在WN18RR数据集的最佳学习率为50。在FB15k-237数据集的最佳学习率为10。实验将批次大小设置为128，负样本数为50，MuRP的曲率设置为c=1。在这些参数下，得到的性能是最佳的。
3.3 MuRP和MuRE对比分析
两个模型在链路预测上的结果如表1所示：
表1 WN18RR和FB15k-237上的链接预测结果
从表中可以观察到，MuRE在非分层的FB15k-237数据集上的性能略好一些，而MuRP在WN18RR上的性能要好。除了HITS@1之外，Mure和MuRP在WN18RR上的所有指标上都超过了之前的最先进的模型。即使在相对较低的嵌入维数(d=40)下，这一点也保持不变，这表明双曲线模型能够简洁地表示多个层次。在FB15k-237中，MuRE的性能仅次于TuckER，这主要是由于跨关系的多任务学习。MuRP并没有包括跨关系多任务学习，这是在未来的工作中亟待解决的问题。
文章比较了MuRE和MuRP在不同度嵌入的WN18RR上的MRR值。当嵌入维度较低时，MuRE和MuRP模型差异最大。MuRP的收敛速度也比MuRE快。实验结果如图2所示：
图2 (a)WN18RR上不同嵌入大小的Mure和MuRP的MRR对数图 (b)Mure和MuRP在WN18RR训练集(虚线)和验证集(实线)上的MRR收敛速度
为了表示模型的每一部分都不可缺少，作者研究了关系特定的转换和偏差选择的消融，实验结果如表2所示：
表2 WN18RR上不同模型架构选择的消融研究：关系转换(左)和偏差(右)。
从表2可以看出，对当前模型架构的任何更改都会对MuRE和MuRP的性能产生负面影响。用嵌入规范化的实体替换偏差会导致MuRP的性能显著降低。
由于并不是WN18RR中的每个关系都在实体上诱导出层次结构，因此该文章研究了由每个关系形成的实体图的层次得分(Khs)，以获得所诱导的层次的度量。该分数仅针对有向网络定义，并且测量其中存在有向路径x→y而不存在y→x的节点对。对于所有有向非循环图，该分数取值为1，对于圈和环，该分数取值为0。对于层次关系，文章还研究了图中任意两个节点之间的最大最短路径和平均最短路径。为了了解哪些关系在双曲空间中嵌入实体中受益最大，实验比较了低维(d=20)实体嵌入的MuRE和MuRP的每个关系的hits@10。最后的对比结果如表3所示：
表3 WN18RR上，d=20时Mure和MuRP的每个关系的hits@10。
从表3中我们可以看到，这两个模型在Khs层次结构得分为0的非层次对称关系性能都比较好，而MuRP在层次关系上的性能优于MuRE。对于形成较深树的关系，MuRE和MuRP之间的性能差异通常较大。
一系列实验结果表明，MuRP在分层多关系数据集上的链路预测任务上优于MuRE和现有模型，并且需要更低的维度就能获得与其欧几里德类似模型相当的性能。在未来，可以研究最近引入的黎曼自适应优化方法与黎曼随机梯度下降方法的影响。此外，由于知识图谱中并不是所有的关系都是分层的，后续工作可以将欧几里得和双曲模型结合起来，产生最适合数据曲率的混合曲率嵌入。
参考资料
原文
https://arxiv.org/abs/1905.09791
代码
https://github.com/ibalazevic/multirelational-poincare
