Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval

Idea

ARK 用极简 graph-native tools 将 KG retrieval 变成自适应交互：agent 随时在全图 lexical search 和一跳 neighborhood exploration 之间切换，逐步 SELECT 证据节点并决定停止。它不预先固定 seed 或 hop depth，并可将大模型探索轨迹蒸馏到小模型以降低推理成本。

Research Problem

相似度检索擅长覆盖广泛文本，却难满足关系链条件；纯 traversal 从少数 seed 开始，一旦种子错误或查询涉及多个分散实体，就容易困在局部邻域。预设固定 hop 数也不适合复杂度不同的问题，训练 graph-specific retriever 则增加迁移与标注成本。

Insight

breadth 和 depth 是同一查询过程中可反复切换的操作，而不是必须先选定的 retrieval paradigm。保留全局搜索使 agent 能重新定位，one-hop tool 的组合提供按需多跳能力；最终按被选中节点的顺序和多条独立探索的共识形成 ranking。

Method

1. 将 KG 节点的 titles、descriptions 等文本建立 BM25 index；Global Search 接收 agent 生成的 subquery，返回全图 top-k candidates，使模型能寻找初始入口或重新 anchoring。
2. Neighborhood Exploration 从给定节点取相邻实体，按可选 node/edge types 过滤并可用 subquery 排序；边方向与类型在输出中暴露，模型通过连续调用形成多跳路径，穿插全图搜索并维护已选节点列表，FINISH 或 budget 达到时结束。
3. 运行多个独立 agent trajectories，将各自排名列表拼接，以节点出现频次排序，平票用最早出现位置处理；研究 tool-call budget 与并行 agent 数对 retrieval robustness 和成本的作用。
4. 用 teacher tool-use traces 做 assistant-token next-token SFT，mask 用户和工具输出，不需要 ground-truth evidence-node labels；在 STaRK 的 AMAZON、MAG、PRIME 上按 Hit@1/5、Recall@20、MRR 比较，并评估 Qwen3-8B 蒸馏结果。