LogosKG：面向硬件优化、可扩展且可解释的知识图谱检索

# LogosKG：面向硬件优化的可扩展可解释知识图谱检索  
来源：https://arxiv.org/html/2604.18913  
He Cheng¹，Yifu Wu¹，Saksham Khatwani¹,²，Maya Kruse¹，Dmitriy Dligach³，Timothy A. Miller⁴,⁵，Majid Afshar⁶，Yanjun Gao¹  
¹ 科罗拉多大学安舒茨医学院 LARK 实验室，² 科罗拉多大学博尔德分校，³ 芝加哥洛约拉大学，⁴ 哈佛医学院，⁵ 波士顿儿童医院，⁶ 威斯康星大学麦迪逊分校  
{he.2.cheng, yanjun.gao}@cuanschutz.edu

###### 摘要  
知识图谱（KG）正被越来越多地集成到大型语言模型（LLM）中，以提供结构化、可验证的推理。多跳检索是其中的核心操作，但现有系统难以在效率、可扩展性和可解释性之间取得平衡。我们提出 LogosKG，一种全新的硬件对齐框架，通过符号化 KG 表示将遍历转化为对主体、客体、关系分解后的高效硬件运算，实现大规模 KG 上的可扩展、可解释 kk-跳检索。为扩展到十亿级边图，LogosKG 融合度感知分区、跨图路由与按需缓存。实验表明，其在不损失检索保真度的前提下，相较 CPU 与 GPU 基线取得显著效率提升。凭借在 KG 检索上的验证性能，我们进一步演示两轮 KG-LLM 交互，展示 LogosKG 如何支持大规模、基于证据地分析 KG 拓扑（如跳数分布、连通性）如何影响结构化生物医学知识与 LLM 诊断推理的对齐，为下一代 KG-LLM 集成打开大门。源代码已开源：https://github.com/LARK-NLP-Lab/LogosKG，在线演示：https://lark-nlp-lab-logoskg.hf.space/。

## 1 引言  
数十年来，知识图谱一直是结构化知识表示的基石，通过关系将概念跨领域链接，如社交网络、生物医学、推荐系统等。随着 LLM 的兴起，KG 作为外部符号知识源重新受到重视，可在检索增强生成、知识验证与推理等任务中弥补 LLM 统计推理的不足。在医疗诊断等高风险场景，LLM 可靠性直接影响患者安全，KG 被用于将模型预测锚定在已验证的生物医学知识上。

表 1：检索系统与库对比。“基于矩阵”指采用线性代数原语进行检索。注：条目为单机默认设计；可扩展性指能否处理超单机内存的图；缺失功能可通过额外处理实现，但耗时耗内存。  
图 1：LogosKG 检索框架概览。LogosKG 采用基于线性代数的检索方法，同时支持小图与大图。对大图，LogosKG 引入图分区、跨图路由与按需缓存，实现分布式子图上的高效多跳检索。检索到的证据可为医疗诊断生成提供知识支撑。

KG 的基本操作是*多跳检索*，即通过中间实体与关系连接远距离概念。传统图遍历算法如 DFS、BFS 在小图上可行，但随图规模增大，代价呈 O(|V|+|E|) 增长，且可达实体随跳深指数级膨胀。内存是另一大瓶颈：实验所用生物医学 KG（UMLS 40.7 万节点、340 万边；PubMedKG 5440 万节点、8650 万边）在遍历前即占用 1.5 GB 与 23.5 GB 内存。UMLS 中一个高度概念两跳扩展（平均 3.3 万 1-跳邻居）可涉及超 10⁹ 条可达边，仅物化邻接信息即需数十 GB 内存。这种遍历与存储的指数级增长构成了可扩展多跳检索的核心系统挑战，迫使先前工作只能在受限子图上运行。

众多系统试图提升检索效率（表 1），聚焦三大维度：1) 基于矩阵的图表示，用矩阵/张量运算替代指针结构，以映射到多核 CPU 或 GPU 等并行硬件（如 GraphBLAS 系统）；2) 可扩展性，通过图分区等机制支持十亿级边图（如 DGL、PyG）；3) 路径重构，支持可解释推理（如 Neo4j、TigerGraph）。然而，大多数系统仅优化其中一到两项，且常依赖分布式基础设施而非单机效率。

我们的思路。为实现可扩展且可解释的 KG 检索，我们提出 LogosKG——一种全新的硬件对齐框架，在系统层面重新思考图遍历（图 1）。虽然符号图推理已有探索，LogosKG 将该方法扩展为统一端到端系统，利用单机硬件在稠密大图上实现高跳遍历，支持连续数据布局与 CPU/GPU 内核级并行。对大图，LogosKG 实现度感知分区与跨图路由，遵循内存局部性原则，辅以按需缓存降低 I/O 开销，复杂度降至 O(|E|log|E|+|T|)。同时，LogosKG 保存中间实体与关系以支持路径重构。这些创新将理论公式转化为实用可扩展的大规模 KG 检索框架。

我们在检索效率、可扩展性与可解释性上对比 LogosKG 与现有库/系统。实验聚焦稠密、语义丰富的生物医学 KG，真实反映稠密连接、异构关系与可解释推理挑战。尽管实验使用生物医学数据，LogosKG 与领域无关，适用于任何大规模结构化图。

LogosKG 消除了可扩展高跳检索的根本系统瓶颈，从而支持研究 LLM 在高跳 KG 上的推理，无论下游选择或推理组件是否可学习。我们通过临床诊断预测场景系统研究 KG-LLM 交互，采用两轮交互考察 LLM 在跳深增加时如何响应 KG 结构。本文贡献总结如下：

- • 大规模 KG 遍历的系统能力：提出 LogosKG，一种硬件对齐框架，在单机硬件上实现确定性、可解释的高跳检索（§3）。  
- • 全面系统评估：在 CPU 与 GPU 基线上评测检索保真度、效率与可扩展性（§5）。  
- • 高跳场景下的 KG-LLM 交互分析：利用 LogosKG 系统研究 LLM 预测与深层 KG 结构的交互（§6）。

LogosKG 可作为高跳 KG 检索的通用系统骨干，支持可学习或不可学习的精炼与推理策略。KG-LLM 交互本身是复杂研究课题，我们在附录（§A.5–A.7）补充了可学习与不可学习高跳 KG-LLM 设计的分析，说明 LogosKG 使此类研究成为可能。

## 2 相关工作  
现有系统与库可按架构分为：数据库引擎、计算库、图分析工具与 GPU 框架。  
数据库引擎（如 Neo4j、TigerGraph）提供丰富查询语言，但需大量分片基础设施，并受查询解析与事务日志运行时开销拖累。  
计算库（如 GraphBLAS）利用稀疏矩阵运算提升多跳检索效率，但因聚合时丢失边来源，原生不支持完整路径重构。  
图分析工具（igraph、NetworkX、SNAP）提供灵活 API，但依赖内存受限的指针追逐算法，扩展性不足。  
GPU 框架（cuGraph、DGL、PyG）支持单机高速计算，但侧重稠密张量训练而非检索，依赖经典搜索后端，多跳推理效率受限。

### 2.1 作为 LLM 验证器的 KG  
LLM 易产生幻觉与未验证断言，促使 KG 用于事实核查。近期方法利用 KG 将文本断言锚定于结构化证据，构建多跳推理链。代表工作包括 FactKG、GraphCheck（长文本事实核查），ClaimVer、Verify-in-the-Graph（可解释证据归因与实体消歧），GraphFC、FactCheck（图推理与 LLM 验证结合）。相比之下，我们直接暴露 KG 原始拓扑，揭示符号知识组织与神经推理间的结构鸿沟。

## 3 LogosKG

### 3.1 问题定义  
知识图谱。KG 定义为有向多关系图 G=(E,R,T)，其中 E 为实体集，R 为关系类型集，T⊆E×R×E 为三元组集。三元组 (e_s,r,e_o)∈T 表示主体实体 e_s 通过关系 r 链接到客体实体 e_o。

kk-跳检索。给定查询 q⊆E，kk-跳检索目标是从任意 e_q∈q 出发，在 k 步关系内可达的所有实体。实际中，大 KG 查询耗时高，任务要求在保持低延迟的同时完成检索。

### 3.2 KG 分解  
为支持高效 kk-跳检索，KG 可用三个稀疏关联矩阵编码主体、客体与关系，将繁重图遍历转为轻量稀疏矩阵运算（图 1）。

主体矩阵。SUB∈{0,1}^{|E|×|T|} 定义为：  
SUB_{i,t} = 1 若实体 e_i 是三元组 t 的主体，否则 0。行对应实体，列对应三元组。

客体矩阵。OBJ∈{0,1}^{|T|×|E|} 定义为：  
OBJ_{t,j} = 1 若实体 e_j 是三元组 t 的客体，否则 0。行对应三元组，列对应实体。

关系矩阵。REL∈{0,1}^{|T|×|R|} 定义为：  
REL_{t,r} = 1 若三元组 t 使用关系 r，否则 0。行对应三元组，列对应关系类型，可在多跳检索中恢复关系路径。

### 3.3 高效检索  
一跳检索。定义查询向量 q^(0)∈{0,1}^{1×|E|}，其中 q^(0)[i]=1 表示实体 e_i 在查询中。