Enhancing Agentic Textual Graph Retrieval with Synthetic Stepwise Supervision

Idea

Graph-S3 为 agentic textual graph retrieval 合成可逐步评价的监督，用经过提炼的 golden subgraphs 指导图探索策略。系统把“扩展邻居”和“保留相关关系”分为不同动作，使检索器逐轮构建紧凑证据子图，再交给答案模块推理。

Research Problem

基于 embedding 的单次检索容易只捕获浅层相关性；交互式图检索虽能处理多跳关系，但动作空间大、人工步骤标注昂贵。仅依据最终答案训练又存在奖励稀疏与 credit assignment 问题：冗余甚至错误步骤也可能碰巧得到正确答案，难以教会有效探索。

Insight

答案正确只能说明最终证据可能够用，不能说明每一步检索合理。先离线从成功轨迹删除冗余路径并形成可检查的目标子图，再评价当前动作与这些证据的关系，可提供比单一终局奖励更密集的学习信号。

Method

1. 定义 Explore Entity、Choose Relation、Finish：Explore 扩展实体邻域并更新 perception window，Choose 从已有窗口筛出问题相关 triples，Finish 将问题与 focused subgraph 交给答案模块。
2. 用 GPT-4o 在图环境中生成带自然语言理由的探索轨迹；状态包含问题、感知窗口、已选子图与动作历史。只保留终局答案符合 ground truth 的轨迹，原始步骤用于 SFT warm-up。
3. 对成功轨迹进行 refinement，寻找保持可行性、终态与正确答案的更短轨迹，删除多余绕行，并将精炼轨迹分解为步骤监督和对应 golden evidence。
4. 先监督学习 thought-action tokens，再用 GRPO 根据动作无效、仅格式正确、部分正确和匹配目标动作等分级规则给奖；推理阶段交替扩展与筛选关系，在证据足够时终止，以控制检索深度和上下文冗余。