笔记整理：吕恬雯，浙江大学研究生，研究方向为大语言模型、AI for Science
论文链接：https://openreview.net/pdf?id=rTCJ29pkuA
发表会议：ICLR 2025
1. 动机
大型语言模型（LLMs）在处理知识图谱（KGs）方面取得了进展，但现有的方法存在很高的非检索率（non-retrieval rate）。这种限制降低了基于知识图谱问答的准确性。
分析表明，贪婪搜索（greedy search）和前向推理（forward reasoning）的结合是导致此问题的主要原因。非检索失败的主要原因可分为三类：
（1）误导（Misdirection）（占68.8%）：即正确的路径与检索到的路径并行，但模型在第一步选错后就很难再找到正确路径。
（2）深度限制（Depth Limitation）（占25.2%）：正确路径的长度超过了最大允许的推理长度。
（3）路径缺失（Path Absence）（占6.0%）。
现有方法的共同限制：
（1）基于子图的检索（subgraph reasoning）：结构化强但理解性弱。
（2）基于 LLM 的迭代推理（LLM reasoning，如 ToG）：理解强但路径容易走偏。两者都依赖单一步的贪心策略，导致错误累积，无法解决误导和深度限制问题。
2. 贡献
本文的主要贡献有：
（1）设计：提出了超关系（super-relations）的概念，即特定领域内一组关系的集合。使用超关系可以通过包含大量关系来进行高效推理，同时增强推理路径的深度和宽度，以解决非检索问题。
（2）框架：提出了一个名为ReKnoS（Reason over Knowledge Graphs with Super-Relations）的新型推理框架。该框架集成了超关系，能同时表示多条关系路径，在不丢弃潜在连接的情况下显著扩展搜索空间。
（3）实验：在九个真实世界的数据集上进行了实验。结果表明，ReKnoS在检索成功率和搜索空间大小方面均显著优于传统方法，平均准确率提高了2.92%。
3. 方法
本文提出的ReKnoS框架旨在利用超关系来扩展搜索并提高检索效率。
（1）核心概念：超关系（Super-Relations）超关系被定义为一组更细粒度的、详细的关系的集合。例如，超关系 "music.featured_artist" 可以包括 "music.featured_artist.recordings" 和 "music.featured_artist.albums" 等具体关系。在Wikidata等知识图谱中，这种层级关系是固有的（例如，将第二级关系视为超关系)。
（2）ReKnoS 框架流程
框架最多包含 L 个推理步骤。
步骤 0：分析器（Analyzer）
从输入问题中提取查询实体（Topic Entity）。
步骤 1...L：推理（Reasoning Steps）
候选选择（Candidate Selection）：在第步，框架首先确定候选超关系集，这些超关系必须与第步选定的超关系集中的至少一个超关系相连。
评分（Scoring）：LLM 对中的所有候选超关系进行评分（范围0到1）。然后，框架选择得分最高的 N 个超关系，组成新的超关系集。
决策与实体提取（Decision & Entity Extraction）：LLM 根据当前检索到的路径和实体，决定是（a）从当前实体中提取答案，还是（b）继续进行下一步推理。
路径选择（Path Selection）：框架会从多条可能的“超关系路径”中，选出得分最高的 K 条路径，路径得分由其包含的超关系得分之和确定。
最终实体选择（Final Entity Selection）：提取满足这 K 条最优超关系路径的最终实体集。
步骤 L+1：积分器（Integrator）
LLM 汇总所有收集到的推理路径和最终实体，生成最终答案。
（3）效率优势与 ToG 等基线方法相比，ReKnoS 的效率更高。ToG 需要评估的路径数随深度呈指数增长（）。而 ReKnoS 在每一步中，LLM 评估的超关系数量最多为 N（即候选集大小），与深度无关，显著减少了LLM的调用次数。
4. 实验
（1）数据集和基线
数据集：使用了9个数据集，涵盖多种KGQA任务，如GrailQA、CWQ、WebQSP、SimpleQA，以及T-REx、HotpotQA等。
基线：包括IO、CoT、Self-Consistency，以及SOTA的KG推理方法：StructGPT、Think-on-Graph (ToG) 和 KG-Agent。
度量标准：主要是 Hits@1（精确匹配准确率）。
（2）核心结果
性能对比：ReKnoS 在大多数数据集上均优于所有基线，尤其是在需要复杂推理的数据集上（如GrailQA和CWQ） 。例如，在GrailQA上，使用GPT-3.5时，ReKnoS (71.9%) 优于 KG-Agent (68.9%)；使用GPT-40-mini时，ReKnoS (80.5%) 优于 KG-Agent (77.5%) 。
超关系分析：ReKnoS 具有明显更大的搜索空间。在GrailQA上，其平均搜索空间大小（即搜索过程中遇到的事实三元组数量）比 KG-Agent 和 ToG 分别高出 42% 和 55%。这使得ReKnoS更有可能检索到正确的答案三元组。
效率分析：ReKnoS 在保持卓越性能的同时，实现了最低的平均LLM调用次数。例如，在WebQSP上，ReKnoS 平均调用 3.7 次，而 ToG 为 15.3 次。ReKnoS的调用次数（）与搜索宽度 N 无关，而 ToG 的调用次数（）则依赖于 N。
超参数分析：增加搜索宽度 N 和最大长度 L 均能带来性能提升。当 N 从 3 降到 1 时，性能显著下降（例如 L=3 时，Hits@1 从 81.1% 降至 76.2%），表明 N（即搜索宽度）对框架性能至关重要。
5. 总结
本文提出了 ReKnoS 框架，该框架利用“超关系”在知识图谱推理过程中包含大量关系。通过实现多关系路径的同时表示和探索，ReKnoS 显著扩展了KG的推理搜索空间，同时避免了有价值信息的丢失。大量实验证明，ReKnoS 的性能超越了现有的SOTA基线，展示了超关系在推进复杂KG推理任务方面的潜力。
OpenKG
OpenKG（中文开放知识图谱）旨在推动以中文为核心的知识图谱数据的开放、互联及众包，并促进知识图谱算法、工具及平台的开源开放。
点击阅读原文，进入 OpenKG 网站。
