今天为大家带来斯坦福大学Jure Leskovec教授课题组发表在NeuIPS上的一篇论文。本文引入了一个框架GQE，以便在不完整的知识图谱上有效地对合取逻辑查询进行预测。在本文的方法中，作者在低维空间中对图节点进行嵌入，并在这个嵌入空间中将逻辑运算符表示为学习过的几何运算（例如平移、旋转）。本文通过在低维嵌入空间中执行逻辑运算，实现了线性时间复杂度的变量查询。
1
介绍
各种各样的异构数据可以自然地表示为各类型实体之间的交互网络，而机器学习的一个基本任务就是使用这种图结构数据来预测节点之间的未观察到的边。然而，这个领域的一个公开挑战是如何开发技术来预测更复杂的图查询，这些查询涉及多个未观察到的边、节点甚至变量，而不仅仅是单个边。
合取查询是本文工作的重点，也是图查询中一个特别有用的集合，它对应于仅使用合取和存在量化运算符的一阶逻辑子集。如图1方框中所示，展示了两个合取逻辑查询的例子。
由于在图结构方面，合取查询允许人们推断节点集之间是否存在子图关系，这使得合取查询成为知识图谱应用的自然焦点。在本文中，作者主要对合取逻辑查询进行预测。例如，给定一个包含药物、疾病和蛋白质之间已知相互作用的不完整的生物学知识图谱，我们可以提出一个合取查询：“哪些蛋白质节点可能与同时具有X和Y症状的疾病相关？“在这个查询中，疾病节点是一个存在的量化变量，也就是说，我们只关心某些疾病将蛋白质节点与这些症状节点X和Y连接起来。这种查询的有效答案对应于子图。然而，由于这个生物相互作用网络中的任何边都可能不被观察到，单纯地回答这个问题将需要枚举所有可能的疾病，运算代价昂贵。
图1：连接图查询的示例
在这里，作者开发了一个基于嵌入的框架——GQE，可以有效地预测不完全知识图谱上的合取查询。它的核心思想是在低维空间中嵌入图节点，并将逻辑算子表示为嵌入空间的几何操作（如平移、旋转）。通过训练，作者可以使用该模型来预测哪些节点可能满足任何有效的合取查询，即使查询涉及到未观察到的边。此外，由于时间复杂度与查询中的边数成线性关系，并且与输入网络的大小有关，因此本文可以有效地进行这种预测。
2
GQE
图2：QGE框架概述
3
实验
3.1、实验设置
作者使用双线性的投影运算框架变体，以及使用TransE和DistMult作为投影操作的变体。所有变量在中使用单层神经网络。作为基线，使用一种经过端到端训练的枚举方法来执行边缘预测（使用双线性、TransE或DistMult），并通过取它们各自边缘可能性的乘积（即一个soft-AND）来对可能满足查询的子图进行评分（使用一个带学习的缩放因子的sigmoid来计算边缘可能性）。
在采样方案中，作者为每个可能的查询DAG结构（图4，底部）抽样固定数量的示例查询。对于每个可能的DAG结构，以随机方式均匀地对查询进行抽样，若采样节点不能满足特定DAG结构，则简单拒绝并重复采样直到得到满足特定查询DAG结构的示例查询。
3.2、实验结果
表1包含了基于双线性变换（即上文的操作给出的公式）、DistMult和TransE的三种GQE变量的性能结果，以及仅训练在边缘预测（表示为边缘训练）的消融模型。总体上，我们可以看到，全双线性模型的性能最好。在图4中，作者对不同类型的查询依赖关系图结构的性能进行了细分，其中长路径是最困难的查询类型，我们可以看到它在复杂查询上的性能非常强（相对于它在简单边缘预测上的性能）。
表2比较了性能最好的GQE模型和基于枚举的最佳性能基线。对于具有绑定变量的查询，枚举基线在计算上是困难的，因此这种比较仅限于没有绑定变量的查询子集。即使在这种受限的环境下，我们也看到GQE的表现始终优于基准。这说明在嵌入空间中执行逻辑运算不仅效率更高，而且是枚举边缘似然乘积的有效替代方法，即使在后者可行的情况下也是如此。
4
总结
作者提出了一个嵌入合取图查询的框架，演示了如何将一个实际的逻辑子集映射到嵌入空间中有效的几何运算。实验表明，作者的方法可以对具有数百万关系的真实世界数据做出准确的预测。当然，这个框架也有局限性：例如，它不能处理逻辑否定或析取，而且也不考虑边缘上的特征。于是，作者的未来方向包括泛化逻辑查询的空间，例如，通过学习几何否定算子，并使用图神经网络来整合节点和边缘上更丰富的特征信息。
代码
https://github.com/williamleif/graphqembed
参考资料
https://arxiv.org/abs/1806.01445
