agcore/design/pdd/25-phase19-knowledge-graph-and-retrieval.md

Phase 19：知识图谱 + 双通道检索

背景与目标

问题空间

agcore v0.3.0 已交付 Phase 0-18，记忆系统具备 KnowledgeStore（页面级内容检索）和 VectorStore（向量语义检索），但缺少实体-关系维度的关联检索能力。用户搜索"X 与什么相关"时，现有系统无法返回实体间的拓扑关系。

docs/note-knowledge-graph-design.md 已记录完整的知识图谱设计，Phase 19 将其落地为可编译、可测试的模块。

目标

• 新增 memory/graph.rs，实现 KnowledgeGraph trait + InMemoryGraph 内存实现
• 扩展 MemoryRetriever 为双通道：KnowledgeStore（内容）+ KnowledgeGraph（实体关系）
• 通过 RetrievalStrategy 枚举控制通道选择（Hybrid / KnowledgeOnly / GraphOnly）
• 统一 RetrievalResult.items 为 Vec<RetrievalItem>，enum 变体区分类别
• 标签管理 API 预留（无自动提取流程，Agent 层显式写入）
• Phase 19 仅提供底层 CRUD 接口，实体/关系的写入由 Agent 层（如 LLM 提取）在后续 Phase 中接入。当前无自动填充流程，需 Agent 显式调用 add_entity/add_relation。

与现有模块的定位关系

KnowledgeStore:  页面级内容（"什么是 X"）    ← Phase 6 已有
VectorStore:     向量语义（相似度检索）       ← Phase 15 已有
KnowledgeGraph:  实体级关系（"X 与什么相关"） ← Phase 19 新增
MemoryRetriever: 统一检索入口               ← Phase 19 扩展为双通道

依赖与优先级

• 依赖：Phase 6（KnowledgeStore）[高]、Phase 15（VectorStore 模式参考）[低]
• 优先级：P0（v0.3.0 最后一个 Phase）
• 预估规模：约 600 行核心 + 200 行测试

---

需求分析

功能需求

ID	需求	优先级
F1	GraphEntity / GraphRelation / RelationDirection 类型定义	P0
F2	KnowledgeGraph trait（10 个 async 方法）	P0
F3	InMemoryGraph 实现（HashMap + Vec + tag_index）	P0
F4	BFS 图遍历（防环、权重衰减、方向过滤）	P0
F5	RetrievalItem / RetrievalStrategy / RetrievalResult 扩展	P0
F6	MemoryRetriever 双通道（tokio::join! 并行）	P0
F7	标签管理（set_entity_tags / find_tags / entity_count_by_tag）	P1（预留）

非功能需求

ID	需求	说明
NF1	零新依赖	纯 std + tokio + 已有 crate
NF2	异步安全	InMemoryGraph 内部 Mutex 保护，trait 方法 async
NF3	类型安全	不新增 MemoryError 变体，复用现有 5 个
NF4	向后兼容	MemoryRetriever::new() 签名不变，可选链式注入 graph
NF5	Breaking change 受控	RetrievalResult.items 类型变化，需在 CHANGELOG 标注

---

方案设计

3.1 数据模型

GraphEntity

/// 图谱实体 —— 表示一个可被关联检索的节点。
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphEntity {
    /// 唯一标识（如 "person:rust-dev-01"）。
    pub id: String,
    /// 实体名称（用于展示和关键词匹配）。
    pub name: String,
    /// 实体类型（"person" | "concept" | "project" | ...）。
    pub entity_type: String,
    /// 一句话描述。
    pub description: String,
    /// 检索标签（全小写，原子词，由 Agent 层显式写入）。
    pub tags: Vec<String>,
    /// 任意附加属性（与 PersistentVectorStore.metadata 保持一致）。
    pub properties: HashMap<String, String>,
}

GraphRelation

/// 图谱关系 —— 连接两个实体的有向边。
///
/// 无 `id` 字段，用 `(source_id, target_id, relation_type)` 三元组唯一标识。
/// 提供 `composite_key()` 作为派生 id，满足未来独立 id 需求。
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphRelation {
    /// 源实体 ID。
    pub source_id: String,
    /// 目标实体 ID。
    pub target_id: String,
    /// 关系类型（"works_on" | "part_of" | "related_to" | ...）。
    pub relation_type: String,
    /// 关系强度 [0.0, 1.0]，用于 BFS 评分衰减。
    pub weight: f32,
}

impl GraphRelation {
    /// 复合键：`source_id:target_id:relation_type`，用于去重和查找。
    pub fn composite_key(&self) -> String {
        format!("{}:{}:{}", self.source_id, self.target_id, self.relation_type)
    }
}

RelationDirection

/// 关系遍历方向。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RelationDirection {
    /// 仅出边：source_id → target_id（默认）。
    Outgoing,
    /// 仅入边：target_id → source_id。
    Incoming,
    /// 双向遍历。
    Both,
}

impl Default for RelationDirection {
    fn default() -> Self {
        Self::Outgoing
    }
}

ScoredEntity

/// 带评分的实体 + 路径信息。
#[derive(Debug, Clone)]
pub struct ScoredEntity {
    pub entity: GraphEntity,
    /// 基于图距离的评分 [0.0, 1.0]，沿路径权重乘积衰减。
    pub score: f32,
    /// 从查询实体到当前实体的 ID 路径（用于可解释性）。
    pub path: Vec<String>,
}

TagConstraints

/// 标签约束配置。
#[derive(Debug, Clone)]
pub struct TagConstraints {
    /// 每个实体最多标签数（默认 8）。
    pub max_tags_per_entity: usize,
}

impl Default for TagConstraints {
    fn default() -> Self {
        Self {
            max_tags_per_entity: 8,
        }
    }
}

3.2 KnowledgeGraph trait

/// 知识图谱抽象 —— 实体-关系存储与图遍历检索。
///
/// 所有方法 `async + Send + Sync`，支持跨 `.await` 调用。
/// 复用 `MemoryError`，不新增变体。
#[async_trait]
pub trait KnowledgeGraph: Send + Sync {
    // ── 实体管理 ──

    /// 添加或更新实体（upsert 语义）。
    async fn add_entity(&self, entity: GraphEntity) -> Result<(), MemoryError>;

    /// 按 ID 获取实体，不存在返回 `Ok(None)`。
    async fn get_entity(&self, id: &str) -> Result<Option<GraphEntity>, MemoryError>;

    /// 删除实体及其所有关联关系。
    async fn remove_entity(&self, id: &str) -> Result<(), MemoryError>;

    // ── 关系管理 ──

    /// 添加关系（若复合键已存在则覆盖 weight）。
    async fn add_relation(&self, relation: GraphRelation) -> Result<(), MemoryError>;

    /// 按复合键删除关系。
    async fn remove_relation(
        &self,
        source_id: &str,
        target_id: &str,
        relation_type: &str,
    ) -> Result<(), MemoryError>;

    /// 从指定实体出发，BFS 遍历 depth 层，返回关联实体（带评分）。
    ///
    /// - `direction`：遍历方向（Outgoing / Incoming / Both）
    /// - `relation_types`：可选过滤，仅遍历指定关系类型
    async fn get_related(
        &self,
        entity_id: &str,
        depth: usize,
        direction: RelationDirection,
        relation_types: Option<&[&str]>,
    ) -> Result<Vec<ScoredEntity>, MemoryError>;

    // ── 检索 ──

    /// 按关键词子串匹配实体（不区分大小写），与 KnowledgeStore.search 一致。
    async fn find_by_keywords(&self, keywords: &[String]) -> Result<Vec<GraphEntity>, MemoryError>;

    // ── 标签管理（预留接口，Agent 层显式写入） ──

    /// 按前缀查找已有标签（用于标签复用）。
    async fn find_tags(&self, prefix: &str) -> Result<Vec<String>, MemoryError>;

    /// 设置实体标签（替换式，保留前 max_tags_per_entity 个）。
    /// 返回实际设置的标签数。
    async fn set_entity_tags(
        &self,
        entity_id: &str,
        tags: Vec<String>,
    ) -> Result<usize, MemoryError>;

    /// 按标签统计实体数量。
    async fn entity_count_by_tag(&self, tag: &str) -> Result<usize, MemoryError>;

    /// 获取标签约束配置。
    fn tag_constraints(&self) -> TagConstraints;
}

3.3 InMemoryGraph 实现

内部结构

/// 内存知识图谱实现 —— 纯内存，无持久化。
///
/// 生命周期跟随实例；持久化路径参考 InMemoryVectorStore → PersistentVectorStore 演进模式。
pub struct InMemoryGraph {
    /// 内部状态（单一锁结构，避免嵌套锁死锁）
    inner: Mutex<GraphInner>,
    /// 标签约束
    constraints: TagConstraints,
}

struct GraphInner {
    /// id → entity
    entities: HashMap<String, GraphEntity>,
    /// 所有关系（线性扫描，实测 5000 条 ≈ 1-50µs，无需邻接表索引）
    relations: Vec<GraphRelation>,
    /// tag → entity_ids（反向索引，用于 find_tags / entity_count_by_tag）
    tag_index: HashMap<String, HashSet<String>>,
}

BFS 遍历算法

async fn get_related(
    &self,
    entity_id: &str,
    depth: usize,
    direction: RelationDirection,
    relation_types: Option<&[&str]>,
) -> Result<Vec<ScoredEntity>, MemoryError> {
    // 1. 验证起点存在
    let inner = self.inner.lock().unwrap();
    if !inner.entities.contains_key(entity_id) {
        return Err(MemoryError::NotFound(entity_id.to_string()));
    }

    // 2. BFS 初始化
    let mut visited: HashSet<String> = HashSet::new();
    let mut result: Vec<ScoredEntity> = Vec::new();
    // 队列：(entity_id, score, path)
    let mut queue: VecDeque<(String, f32, Vec<String>)> = VecDeque::new();

    queue.push_back((entity_id.to_string(), 1.0, vec![entity_id.to_string()]));
    visited.insert(entity_id.to_string());

    // 3. BFS 逐层遍历
    for _ in 0..depth {
        let mut next_queue: VecDeque<(String, f32, Vec<String>)> = VecDeque::new();

        while let Some((current_id, score, path)) = queue.pop_front() {
            // 筛选与 current_id 相关的关系
            for rel in inner.relations.iter() {
                // 方向过滤
                let (match_source, match_target) = match direction {
                    RelationDirection::Outgoing => (&rel.source_id, &rel.target_id),
                    RelationDirection::Incoming => (&rel.target_id, &rel.source_id),
                    RelationDirection::Both => {
                        if rel.source_id == current_id {
                            (&rel.source_id, &rel.target_id)
                        } else if rel.target_id == current_id {
                            (&rel.target_id, &rel.source_id)
                        } else {
                            continue;
                        }
                    }
                };

                if *match_source != current_id {
                    continue;
                }

                // 关系类型过滤
                if let Some(types) = relation_types {
                    if !types.contains(&rel.relation_type.as_str()) {
                        continue;
                    }
                }

                let neighbor_id = match_target.clone();
                if visited.contains(&neighbor_id) {
                    continue;
                }
                visited.insert(neighbor_id.clone());

                // 权重乘积衰减
                let new_score = score * rel.weight;
                let mut new_path = path.clone();
                new_path.push(neighbor_id.clone());

                result.push(ScoredEntity {
                    entity: inner.entities.get(&neighbor_id).cloned()
                        .ok_or_else(|| MemoryError::NotFound(neighbor_id.clone()))?,
                    score: new_score,
                    path: new_path.clone(),
                });

                next_queue.push_back((neighbor_id, new_score, new_path));
            }
        }

        queue = next_queue;
    }

    // 4. 按分数降序排列
    result.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal));
    Ok(result)
}

depth=0 时仅验证起点实体存在，返回空关联列表（不遍历任何边）。

BFS 关键设计点：

特性	处理方式
环路	visited: HashSet<String> 已访问集合防环
评分衰减	沿路径 score *= rel.weight，权重乘积
多路径	BFS 天然先到先得，同一实体只保留首次到达路径
关系类型过滤	relation_types: Option<&[&str]>，None 表示不过滤
方向过滤	RelationDirection 枚举，Both 时双向检查

以上性能数据为基于算法复杂度的估算值（O(R) 线性扫描，R=关系数），实际性能需通过基准测试验证。建议在实现后添加 #[bench] 或 criterion 基准测试。

3.4 检索扩展

RetrievalStrategy

/// 检索策略 —— 控制双通道分流。
#[derive(Debug, Clone, Default)]
pub enum RetrievalStrategy {
    /// 并行 KnowledgeStore + KnowledgeGraph，合并排序（默认）。
    #[default]
    Hybrid,
    /// 仅 KnowledgeStore。
    KnowledgeOnly,
    /// 仅 KnowledgeGraph。
    GraphOnly,
}

RetrievalItem

/// 统一检索条目 —— enum 变体区分类别，两通道分数均在 [0,1] 区间。
#[derive(Debug, Clone)]
pub enum RetrievalItem {
    /// 知识页面（来自 KnowledgeStore）。
    KnowledgePage {
        page: KnowledgePage,
        /// TextOverlap 评分 [0.0, 1.0]。
        score: f32,
    },
    /// 图谱实体（来自 KnowledgeGraph）。
    GraphEntity {
        entity: crate::memory::graph::GraphEntity,
        /// 图距离评分 [0.0, 1.0]。
        score: f32,
        /// 从查询实体到当前实体的 ID 路径。
        path: Vec<String>,
    },
}

impl RetrievalItem {
    /// 统一分数（用于合并排序）。
    pub fn score(&self) -> f32 {
        match self {
            Self::KnowledgePage { score, .. } => *score,
            Self::GraphEntity { score, .. } => *score,
        }
    }
}

注意：两个通道的分数维度不同（TextOverlap vs 图距离），合并排序仅用于统一返回，不代表跨通道可比性。

向后兼容导出（ScoredItem）

// ── 向后兼容导出 ──

/// 旧版带评分的知识页面检索结果（已废弃）。
///
/// 请迁移到 `RetrievalItem::KnowledgePage { page, score }`。
#[deprecated(since = "0.3.0", note = "使用 RetrievalItem::KnowledgePage 代替")]
#[derive(Debug, Clone)]
pub struct ScoredItem {
    pub page: KnowledgePage,
    pub score: f32,
}

// 在 memory.rs 模块根的重导出中保留：
// #[allow(deprecated)]
// pub use retriever::ScoredItem;

RetrievalResult 更新

/// 检索结果。
#[derive(Debug, Clone)]
pub struct RetrievalResult {
    /// 统一条目列表，按分数降序排列。
    pub items: Vec<RetrievalItem>,
    pub query: String,
    /// 本次检索实际执行的策略（可能因 graph 未注入而退化），而非用户通过 `with_strategy()` 配置的值。
    pub strategy: RetrievalStrategy,
}

MemoryRetriever 扩展

pub struct MemoryRetriever {
    knowledge_store: KnowledgeStore,
    /// 可选知识图谱（None 时退化为单通道）。
    knowledge_graph: Option<Arc<dyn KnowledgeGraph>>,
    /// 检索策略（默认 Hybrid）。
    strategy: RetrievalStrategy,
    config: RetrieverConfig,
    stop_words: HashSet<String>,
}

impl MemoryRetriever {
    /// 创建新的 MemoryRetriever（保持向后兼容）。
    pub fn new(knowledge_store: KnowledgeStore, config: RetrieverConfig) -> Self {
        Self {
            knowledge_store,
            knowledge_graph: None,
            strategy: RetrievalStrategy::default(),
            config,
            stop_words: default_stop_words(),
        }
    }

    /// 注入知识图谱，启用双通道检索。
    pub fn with_knowledge_graph(mut self, graph: Arc<dyn KnowledgeGraph>) -> Self {
        self.knowledge_graph = Some(graph);
        self
    }

    /// 设置检索策略。
    pub fn with_strategy(mut self, strategy: RetrievalStrategy) -> Self {
        self.strategy = strategy;
        self
    }

    /// 检索相关记忆（双通道）。
    pub async fn retrieve(&self, query: &str) -> Result<RetrievalResult, MemoryError> {
        if query.is_empty() {
            return Ok(RetrievalResult {
                items: Vec::new(),
                query: query.to_string(),
                strategy: self.strategy.clone(),
            });
        }

        let keywords = extract_keywords(query, &self.stop_words);
        let has_graph = self.knowledge_graph.is_some();

        // 按策略分流
        match (&self.strategy, has_graph) {
            // 仅知识页面
            (RetrievalStrategy::KnowledgeOnly, _) | (_, false) => {
                let items = self.search_knowledge_store(query, &keywords).await?;
                Ok(RetrievalResult {
                    items,
                    query: query.to_string(),
                    strategy: RetrievalStrategy::KnowledgeOnly,
                })
            }
            // 仅图谱
            (RetrievalStrategy::GraphOnly, true) => {
                let graph = self.knowledge_graph.as_ref().unwrap();
                let items = self.search_graph(query, &keywords, graph).await?;
                Ok(RetrievalResult {
                    items,
                    query: query.to_string(),
                    strategy: self.strategy.clone(),
                })
            }
            // 混合：并行执行，合并排序
            (RetrievalStrategy::Hybrid, true) => {
                let graph = self.knowledge_graph.as_ref().unwrap();
                let (kp_items, g_items) = tokio::join!(
                    self.search_knowledge_store(query, &keywords),
                    self.search_graph(query, &keywords, graph),
                );

                let mut items = kp_items?;
                items.extend(g_items?);
                items.sort_by(|a, b| {
                    b.score().partial_cmp(&a.score())
                        .unwrap_or(std::cmp::Ordering::Equal)
                });
                items.truncate(self.config.max_results);

                Ok(RetrievalResult {
                    items,
                    query: query.to_string(),
                    strategy: self.strategy.clone(),
                })
            }
        }
    }
}

3.5 标签管理

标签索引维护

tag_index: HashMap<String, HashSet<String>> 维护 tag → entity_ids 反向映射：

• set_entity_tags：先清除旧标签的反向引用，再写入新标签。超出 max_tags_per_entity 时截断。
• find_tags：遍历 tag_index.keys()，按前缀过滤。
• entity_count_by_tag：直接返回 tag_index.get(tag).map_or(0, |s| s.len())。

实现要点

async fn set_entity_tags(
    &self,
    entity_id: &str,
    tags: Vec<String>,
) -> Result<usize, MemoryError> {
    let mut inner = self.inner.lock().unwrap();
    let entity = inner.entities.get_mut(entity_id)
        .ok_or_else(|| MemoryError::NotFound(entity_id.to_string()))?;

    // 清除旧标签的反向引用
    for old_tag in &entity.tags {
        if let Some(ids) = inner.tag_index.get_mut(old_tag) {
            ids.remove(entity_id);
            if ids.is_empty() {
                inner.tag_index.remove(old_tag);
            }
        }
    }

    // 截断到 max_tags_per_entity
    let max = self.constraints.max_tags_per_entity;
    let new_tags: Vec<String> = tags.into_iter().take(max).collect();

    // 写入新标签的反向引用
    for tag in &new_tags {
        inner.tag_index.entry(tag.clone())
            .or_default()
            .insert(entity_id.to_string());
    }

    entity.tags = new_tags.clone();
    Ok(new_tags.len())
}

标签复用流程（文档说明）

LLM 提取候选标签 → 对每个候选:
  graph.find_tags(candidate.lowercase())
    ├─ 命中已有标签 → 复用
    └─ 无匹配 → 注册新标签

标注：当前无自动提取流程，需 Agent 层显式调用 set_entity_tags。

---

实现计划

Step	内容	文件范围	验证标准	预估行数
1	graph.rs 核心类型：GraphEntity / GraphRelation / RelationDirection / ScoredEntity / TagConstraints	src/memory/graph.rs	cargo check 编译通过	~80
2	KnowledgeGraph trait 定义（10 个 async 方法）	src/memory/graph.rs	trait 编译通过，无未实现方法	~90
3	InMemoryGraph 实现 + BFS 遍历	src/memory/graph.rs	单元测试：添加实体/关系、BFS 遍历、方向过滤、类型过滤	~250
4	标签管理实现（set_entity_tags / find_tags / entity_count_by_tag）	src/memory/graph.rs	单元测试：标签增删查、截断、反向索引维护	~80
5	retriever.rs 扩展：RetrievalItem / RetrievalStrategy / MemoryRetriever 改造	src/memory/retriever.rs	cargo check + 双通道检索测试	~180
6	memory.rs 模块根更新 + 重导出	src/memory.rs	cargo check，pub use 无编译错误	~10
7	内联测试	src/memory/graph.rs + src/memory/retriever.rs	cargo test --all-targets 全绿	~150

总预估：约 840 行（核心 640 + 测试 200）

---

风险评估

风险	影响	缓解措施
标签 API 无消费者	低 — 预留接口，不影响核心功能	文档标注"Agent 层显式写入"，后续 Phase 接入
评分不可比	中 — TextOverlap vs 图距离维度不同	RetrievalItem enum 变体分离，合并排序仅统一返回，文档注明维度差异
BFS 性能	低 — 5000 关系遍历 ≈ 1-50µs	不引入邻接表索引，等实测超过 1ms 再优化
Breaking change	中 — RetrievalResult.items 类型变化	CHANGELOG 标注，ScoredItem 保留为 pub 兼容导出（deprecate）
Mutex 竞争	低 — InMemoryGraph 单实例场景	读多写少， Mutex 性能足够；后续可升级 RwLock

---

验收标准

检查项	标准	验证命令
编译	0 error	cargo check --all-targets
测试	全绿，测试数从 ~391 增至 ~410+	cargo test --all-targets
Clippy	0 warning	cargo clippy --all-targets -- -D warnings
文档	0 warning	cargo doc --no-deps
BFS 覆盖	所有边界条件：空图、单实体、环路、深度 0、方向过滤、类型过滤	内联测试
双通道	Hybrid / KnowledgeOnly / GraphOnly 三种策略功能正确	内联测试
向后兼容	MemoryRetriever::new() 签名不变，现有调用无需修改	cargo check 无 breaking error