神经图推理：复杂逻辑查询回答的综述

复杂逻辑查询回答 (CLQA) 是近年来图机器学习中出现的一项任务，超越了简单的一跳链路预测，解决了在庞大且可能不完整的图上进行多跳逻辑推理这一更为复杂的任务。该任务在学术界获得了显著关注，许多研究工作在理论和实践层面扩展了这一领域，旨在通过高效的系统解决不同类型的复杂查询和图的各种模式。在本文中，我们提供了一个全面的 CLQA 综述，详细的分类法从多个角度研究了该领域，包括图类型（模态、推理领域、背景语义）、建模方面（编码器、处理器、解码器）、支持的查询（操作符、模式、投影变量）、数据集、评估指标和应用。最后，我们指出了 CLQA 未来研究的有前景的方向、未解决的问题和应用。

1. 引言

数据库（Graph DBs）是捕获、组织和导航现实世界实体的结构化关系信息的关键架构。与传统的关系数据库（Relational DBs）将信息存储在具有固定模式的表格中不同，图数据库以异质图的形式存储信息，其中节点表示实体，边表示实体之间的关系。在图数据库中，关系（即实体之间的异质连接）是第一类公民。借助图结构和更加灵活的模式，图数据库能够高效且富有表现力地处理遥远实体之间的高阶关系，特别是在多跳层次结构中进行导航。传统数据库通常需要昂贵的连接操作来检索信息，而图数据库则可以直接遍历图并通过链接更高效地进行导航。由于其强大的能力，图数据库已成为许多关键工业应用的基础，包括虚拟助手中的问题回答（Flint, 2021; Ilyas 等, 2022）、市场中的推荐系统（Dong, 2018; Hamad 等, 2018）、移动应用中的社交网络（Bronson 等, 2013）以及金融行业中的欺诈检测（Tian 等, 2019; Pourhabibi 等, 2020）。 图数据库的一个重要任务是执行复杂的查询回答。其目标是从图数据库中检索给定输入查询的答案。给定查询后，图数据库首先通过查询规划器将查询转换并优化为更高效的图遍历模式，然后通过查询执行器在图数据库上执行该模式，从图存储中检索答案。存储将图压缩成适用于快速表查找的符号索引。因此，查询在假设图的完整性的情况下非常快速和高效，即假设存储的图没有缺失的边。 然而，大多数现实世界的图通常是不完整的。例如，在 Freebase 中，93.8% 的人没有出生地，78.5% 的人没有国籍（Mintz 等, 2009），约 68% 的人没有职业（West 等, 2014）；而在 Wikidata 中，约 50% 的艺术家没有出生日期（Zhang 等, 2022a），仅 0.4% 的已知建筑物有关于高度的信息（Ho 等, 2022）。鉴于这种不完整性，单纯地遍历图来查找答案会导致显著遗漏相关结果，且随着查询复杂度的增加，问题进一步加剧。这本质上阻碍了图数据库的应用。链路预测旨在预测缺失的信息，但这是一项具有挑战性的任务。先前的研究通过学习实体或链路的潜在表示（Bordes 等, 2013；Yang 等, 2015；Trouillon 等, 2016；Sun 等, 2019）或挖掘规则（Galárraga 等, 2013；Xiong 等, 2017；Lin 等, 2018；Qu 等, 2021）来预测链路。虽然可以使用一跳链路预测器来实现所有预测的事实（高于某一置信度阈值），并运行确定性的查询回答管道，但该操作的计算复杂度在实体数量上是二次方的，并且对于任何现实世界的图来说都是过于昂贵的。此外，这些方法对完成的可能候选进行排序，意味着它们不能告诉我们哪些完成的结果可以被遍历。推理也可以用来补全特定的信息，但总是存在可能的不完全结果与可判定性之间的权衡——在更密集的图中，一些 SPARQL 推理机制（Hawke 等, 2013）并不保证查询执行在有限时间内终止。 另一方面，图机器学习的最新进展使得能够在潜在空间中进行图的大规模推理，而不会遇到可判定性瓶颈。Hamilton 等人（2018）关于图查询嵌入（Graph Query Embedding, GQE）的开创性工作奠定了在不完整知识图（KGs）上回答复杂数据库式逻辑查询的基础，其中查询执行过程中通过实体、关系和逻辑操作符的参数化来推断缺失的链路，参数化是通过可学习的向量表示和神经网络来实现的。以（图 1）中的不完整知识图为例，给定复杂查询“深度学习领域的图灵奖得主在哪些大学工作？”，传统的符号图数据库（如 SPARQL 或 Cypher）只能返回一个答案（UofT），这是通过边遍历可达的。而神经查询嵌入将图和查询都参数化为嵌入空间中的可学习向量。神经查询执行类似于在嵌入空间中遍历图并执行逻辑操作符，这样就能推断缺失的链路并通过增加两个相关答案（UdeM 和 NYU）来丰富答案集，而这些答案是符号数据库无法获得的。自那时以来，该领域已引起了广泛关注，并对支持的逻辑操作符、查询类型、图模态和建模方法等方面进行了众多改进。我们认为，这些改进尚显零散，缺乏一个整体的目标。至今，仍然缺乏一个统一的框架来组织现有的工作并指导未来的研究。为此，我们提出了该领域的首个全面研究。从概念上讲，我们设计了一个 CLQA 方法的分类法，涵盖了查询回答的各个方面，旨在成为数据管理与机器学习社区之间的桥梁。该分类法（第 3 节）从三个主要维度对现有工作进行了分类：（i）图（第 4 节——基础图及其模式背后的逻辑形式化） （ii）建模（第 5 节——回答查询的神经方法） （iii）查询（第 6 节——可以回答的查询）。接着，我们讨论了数据集和评估指标（第 7 节——如何衡量查询回答的性能）。每个维度进一步细分为更具体的方面。最后，我们讨论了 CLQA 应用（第 8 节），并总结了未来研究的开放挑战（第 9 节）。

相关工作

虽然已有一些关于通用图机器学习（Chami 等, 2022）、知识图中的简单链路预测（Ali 等, 2021；Chen 等, 2023）和基于逻辑的链路预测（Zhang 等, 2022b；Delong 等, 2024）的有益综述，但复杂查询回答领域迄今尚未有相关综述。通过我们的工作，我们填补了这一空白，并提供了该新兴领域的全面视角。我们还在附录 B 中详细阐述了 CLQA 和基于知识图的问答（KGQA，NLP 的另一个子领域）之间的异同。