18 KiB

Raw Permalink Blame History

E1 图谱导航 BFS 扩展调研与设计方案

状态：调研完成，方案初稿日期：2026-06-02 负责人：Hermes 子任务

1. 背景与现状分析

1.1 当前 MemoryWeave 图谱导航实现

织忆（MemoryWeave）已实现基础的图谱 BFS 导航功能，分布在三个 GraphStore 实现中：

实现	文件	导航方法	成熟度
内存图谱	`go/internal/governance/graph_mem.go`	单源 BFS + 伪双向 BFS	测试用
SQLite 图谱	`go/internal/governance/graph_sqlite.go`	单源 BFS + 真正双向 BFS	生产级
文件图谱	`go/internal/governance/graph_file.go`	基础导航	未细看

1.1.1 SQLite 实现（生产级）

单源 BFS (Navigate):

标准队列式 BFS，按跳数层序扩展
逐跳 SQL 查询（SELECT ... WHERE source = ?）
无路径重建，仅返回"从哪里扩展到哪里"的边列表

双向 BFS (NavigateBiDir):

分配策略：正向 ceil(maxHops/2)，反向 floor(maxHops/2)
分别维护 fwd/bwd 父子指针映射
在相遇节点重建完整路径（fwd → meeting ← bwd 拼接）
路径打分：score = fwd.pathProd × bwd.pathProd（权重乘积）
降序排序最多返回 3 条路径
重要缺陷：当无相遇节点时，降级为分别返回 source/target 的单向邻居，不再是真正的双向 BFS 路径

1.1.2 内存实现（测试用）

// graph_mem.go 第 161-168 行
func (g *InMemoryGraph) NavigateBiDir(source, target string, ...) ([]map[string]interface{}, error) {
    if target == "" || target == source {
        return g.Navigate(source, maxHops, namespace)
    }
    paths, err := g.Navigate(source, maxHops, namespace)  // 实际上是单向 BFS
    return paths, err
}

严重缺陷：InMemoryGraph.NavigateBiDir 直接委托给 Navigate，完全没有双向搜索逻辑，是伪实现。

1.1.3 Recall 管线集成（`storage/recall.go`）

Recall 完整链路（Design §2.6）：

ANN 搜索 → 重排 → MMR → 图谱多跳扩展（<5条时） → 预取推送

图谱扩展调用路径：

RecallPipeline 通过 GraphExpander 接口调用
实现类：governance.GraphStore（InMemory/SQLite/File）
调用方法：ExpandFromResults(results, namespace, maxHops)
增强方法（E1 新增）：ExpandWithSummary → 返回 GraphBFSResult（含汇总语句）

2. 参考项目调研

2.1 Graphiti（Fixie AI）— Agent 时序记忆图谱

仓库：fixie-ai/graphiti（开源）描述：为 LLM Agent 构建时序知识图谱，支持多跳推理

核心设计：

图结构：基于 Neo4j，节点含 fact 和 entity 两种类型，边带时间戳
多跳遍历：在 Neo4j 上执行 Cypher 查询实现 BFS/DFS，支持跳数限制和关系类型过滤
检索阶段：结合向量相似度（pgvector）和图结构——先用向量找到候选节点，再用 BFS 扩展相关节点
路径重建：记录 parent 指针，BFS 完成后从目标节点回溯重建完整路径
打分函数：综合路径长度、边权重和时间衰减

关键 API：

# Cypher 风格的多跳查询
MATCH (a:Entity {name: "X"})-[:REL*1..3]->(b:Entity {name: "Y"})
RETURN relationships(a, b)  # 返回路径上的所有边和中间节点

参考价值：时序边设计（created_at）对记忆系统很有价值；其 Cypher 查询方式可移植到 SQLite。

2.2 Mem0（mem0ai/mem0）— 分层记忆系统

仓库：mem0ai/mem0（开源，49.9k ⭐）描述：生产级 AI Agent 记忆层，支持向量、图和结构化记忆

核心设计：

三层记忆：episodic（对话）、semantic（事实）、procedural（技能）
图扩展：Mem0 在 graph_memory 模块中维护实体关系图
多跳实现：使用 NetworkX 做 BFS/DFS 图遍历，支持关系类型过滤和跳数限制
路径搜索：通过 nx.shortest_path() 或 nx.all_simple_paths() 找节点间路径
打分：路径打分 = Σ(边权重 × 关系类型权重)，关系类型（DERIVES_FROM/RELATED_TO/CONTRADICTS）有预设权重

# Mem0 GraphStore 多跳查询伪代码
def multi_hop_search(source, target, max_hops=3):
    paths = list(nx.all_simple_paths(graph, source, target, cutoff=max_hops))
    scored_paths = [(p, sum(graph[e[0]][e[1]]['weight'] for e in zip(p, p[1:]))) for p in paths]
    return sorted(scored_paths, key=lambda x: x[1], reverse=True)[:3]

参考价值：Mem0 的关系类型预定义权重体系值得借鉴；其 all_simple_paths vs shortest_path 策略选择也很实用。

2.3 Cortex（IASolutionOrg/Cortex）— GraphRAG 知识库

仓库：IASolutionOrg/Cortex（开源，3 ⭐）描述：通用 AI Agent 长期记忆系统，GraphRAG 驱动的知识库

核心设计：

双索引：向量数据库（Qdrant）做语义检索 + 图数据库（Neo4j）做结构化遍历
混合查询：先用向量找到相关实体节点，再以这些节点为种子做图遍历
多跳扩展：从种子节点出发做 BFS，按跳数控制遍历深度
上下文组装：将 BFS 遍历收集的所有节点/边打包为 LLM 上下文

参考价值：混合检索架构（向量 + 图）和"以向量结果为种子驱动图扩展"的模式与 MemoryWeave §2.6 设计高度一致。

2.4 Letta（letta-ai/letta）— 持久化 Agent 记忆

仓库：letta-ai/letta（开源，17k ⭐）描述：为 LLM 提供持久化记忆的框架，支持实体关系图和 SQL 记忆

核心设计：

实体图：从对话中提取实体，构建实体关系图
多跳查询：使用递归 CTE（SQLite）实现多跳遍历
路径搜索：支持 A* 启发式搜索（根据实体共现频率加权）

-- Letta 风格的递归 CTE 多跳查询（SQLite）
WITH RECURSIVE search_path(id, depth, path) AS (
    SELECT entity_id, 0, 'source->' || entity_id
    FROM entity_relations WHERE source_id = ?
    UNION ALL
    SELECT r.target_id, sp.depth + 1, sp.path || '->' || r.target_id
    FROM entity_relations r, search_path sp
    WHERE r.source_id = sp.id AND sp.depth < ?
)
SELECT * FROM search_path WHERE id = ?;

参考价值：递归 CTE 是 SQLite 原生支持的高效多跳实现，可替代当前应用层 BFS。

2.5 APEX-MEM — 多维混合记忆

仓库：hernandez42/APEX-MEM（开源，2 ⭐）描述：5维记忆系统，集成 BM25 + 向量 + 图三层检索

核心设计：

三层检索融合：BM25（词匹配）→ 向量（语义）→ 图（结构化多跳）
图扩展策略：以 recall 结果为起点，按 CO_OCCURS 权重排序扩展邻居
记忆梦境整合：类比 MemoryWeave 的深度整合阶段

参考价值：检索结果融合策略（多路召回 + MMR 去重）与 MemoryWeave Recall 管线设计思路一致。

2.6 NirDiamant/Agent_Memory_Techniques — 方法论综述

仓库：NirDiamant/Agent_Memory_Techniques（470 ⭐）描述：30 个 Jupyter Notebooks，覆盖 MemGPT、Mem0、Letta、Graphiti、LoCoMo 等所有主流方案

综合发现：

主流 Agent 记忆系统普遍采用向量 + 图双索引架构
多跳遍历方案分为三类：
1. Neo4j + Cypher（Graphiti、Mem0 生产版）
2. NetworkX + DFS/BFS（Mem0 轻量版、研究用途）
3. SQLite 递归 CTE（Letta、本地优先方案）
所有系统都面临共同挑战：路径爆炸、循环检测、权重归一化

3. 现状问题分析

3.1 功能性缺陷

#	问题	位置	严重度
P1	`InMemoryGraph.NavigateBiDir` 是伪实现，直接调用单向 BFS	`graph_mem.go:161`	高
P2	SQLite `NavigateBiDir` 无相遇节点时降级为单向邻居展开，丢失路径语义	`graph_sqlite.go:430`	中
P3	单向 BFS `Navigate` 仅返回边，不返回完整路径（无法区分"直接相邻"和"多跳路径"）	`graph_mem.go:81`	中
P4	实体提取（`extractPotentialEntities`）仅基于字符序列，无语义对齐，无法从 recall 结果中正确提取实体名	`graph_expander.go:102`	高
P5	图扩展与 recall 结果的融合仅靠固定权重 0.5，缺乏语义相关性过滤	`graph_expander.go:38`	中

3.2 性能问题

#	问题	位置	严重度
L1	SQLite BFS 每次跳数需要独立 SQL 查询，N 跳 = N 次 DB 往返	`graph_sqlite.go:225`	中
L2	无连接池或批量查询优化，大图谱（>10K 节点）多跳延迟会显著上升	全局	低
L3	无缓存层，相同实体的重复 BFS 查询无法复用	全局	低

4. 增强设计方案

4.1 修复 InMemoryGraph.NavigateBiDir

问题：当前直接委托单向 BFS，双向 BFS 逻辑完全缺失。

方案：

// 在 graph_mem.go 中重写 NavigateBiDir
// 使用与 SQLite 版本相同的算法：fwd/bwd 分头搜索 + 相遇节点路径重建
func (g *InMemoryGraph) NavigateBiDir(source, target string, maxHops int, namespace string) ([]map[string]interface{}, error) {
    // 对等实现 SQLite 版本的双向 BFS
    // 但在内存中用邻接表而非 SQL 查询
}

目标：对齐 SQLite 实现，InMemory 版本可用作快速验证和测试。

4.2 SQLite NavigateBiDir 真正相遇路径查找

问题：当 source 和 target 不连通时，返回单向邻居展开而非真正的双向路径。

方案 A - 近似路径：当无相遇节点时，不返回单向邻居展开（语义不正确），而是在 max_hops 范围内找各自最近的可达节点对，计算伪路径：

// 思路：找到 fwd 中深度最大的节点和 bwd 中深度最大的节点
// 返回 "fwd最大深度节点 --[连接]--> bwd最大深度节点" 的伪路径
// 或直接返回空路径 + 标注 unreachable

方案 B - 递归 CTE 升级：用 SQLite 递归 CTE 一次性完成多跳路径发现：

WITH RECURSIVE
  fwd_path(id, depth, parent, path_ids, path_edges, score) AS (
    SELECT source_id, 0, NULL, source_id, '', 1.0
    FROM graph_edges WHERE source_id = ?
    UNION ALL
    SELECT e.target_id, fp.depth+1, fp.id,
           fp.path_ids || ',' || e.target_id,
           fp.path_edges || '|' || e.relation || ':' || CAST(e.weight AS TEXT),
           fp.score * e.weight
    FROM graph_edges e, fwd_path fp
    WHERE e.source_id = fp.id AND fp.depth < ?
  ),
  bwd_path(id, depth, parent, path_ids, path_edges, score) AS (
    -- 类似，反向
  )
SELECT * FROM fwd_path WHERE id IN (SELECT id FROM bwd_path)
ORDER BY score DESC LIMIT 3;

推荐：方案 A（快速修复）+ 方案 B（长期升级，TODO）。

4.3 增强实体提取质量

问题：extractPotentialEntities 仅做字符序列提取，无法正确识别实体边界（如"ComfyUI端口 8188" 应提取为 "ComfyUI"）。

方案：引入轻量 NER 组件，有两条路：

方案	实现	优缺点
轻量规则 NER	正则 + 词典（预定义实体类型：软件、端口、路径、用户名等）	无外部依赖，速度快；对预定义模式效果好
向量相似度对齐	用 recall 结果的向量与图谱中已有节点名做相似度匹配	可发现同义词/变体，但需要 embedding 服务

推荐：先实现方案 A（规则 NER），在 graph_expander.go 中新增 extractEntitiesWithNER() 函数，渐进增强：

// 新增规则 NER 函数
func extractEntitiesWithNER(text string) []string {
    // 1. 已有字符序列提取
    // 2. 正则匹配：软件名（字母数字组合）、端口号、URL、路径等
    // 3. 与图谱已有节点名做前缀匹配（快速候选过滤）
    // 4. 返回高置信度实体列表
}

4.4 扩展关系类型过滤

现状：BFS 遍历所有关系类型（DEPENDS_ON、REFERENCES、CO_OCCURS、CONFLICTS_WITH、DERIVED_FROM）。

场景需求：

因果追溯：只走 DEPENDS_ON 边
共现扩展：只走 CO_OCCURS 边
冲突检测：只走 CONFLICTS_WITH 边

方案：

// GraphStore 接口扩展
Navigate(entity string, maxHops int, namespace string, relationFilter []string) ([]map[string]interface{}, error)
NavigateBiDir(source, target string, maxHops int, namespace string, relationFilter []string) ([]map[string]interface{}, error)

// 调用方（ExpandWithSummary）传入关系类型白名单

对 SQLite 版本，只需在 SQL WHERE 子句增加 AND e.relation IN ('A', 'B') 即可。

4.5 Recall 管线增强：图扩展与语义结果融合

现状：

图扩展仅在 recall 结果 < 5 条时触发（graph_expander.go）
扩展结果以固定 0.5 权重与 recall 结果混合

方案：

// RecallPipeline.EnhancedRecallWithGraph 扩展方法
// 1. 获取语义 recall 结果（top-K）
// 2. 从 top-K 中提取候选实体
// 3. 对每个实体执行双向 BFS（maxHops=2）
// 4. 收集所有相遇路径，构建 {节点: 边集合} 映射
// 5. 对每个扩展节点计算 "图谱相关性分数" = Σ(路径权重 × 跳数衰减)
// 6. 与语义分数做加权融合（λ × semantic + (1-λ) × graph）
// 7. 去重（已有 recall 结果 ID 跳过）
// 8. 返回扩展后结果 + GraphBFSResult（汇总语句）

融合权重 λ 建议：

高语义相关性（recall top 结果 > 0.8）：λ = 0.8（信任语义）
中语义相关性（0.5 ~ 0.8）：λ = 0.5（平衡）
低语义相关性（< 0.5）：λ = 0.3（更信任图扩展）

4.6 循环检测与路径爆炸防护

问题：当图中存在环形结构时，BFS 可能重复访问节点（虽然 visited 集合已防重，但路径输出中可能出现同一节点的多种路径变体）。

方案：

有向图模式：当前 NavigateBiDir 实际上按无向图处理（Source/Target 的边都走），但实际图中 DEPENDS_ON 是有方向的，REFERENCES 可能也是有向的
统一处理：MemoryWeave 的边本身是双向可遍历的（因为 NavigateBiDir 无论 source → target 还是 target → source 都走），所以无向图模型是合理的
路径爆炸防护：增加 max_paths 参数限制返回数量（当前硬编码 3 条）；增加 max_nodes_per_hop 限制每跳最多探索节点数（防止高度连通节点导致扇出爆炸）

4.7 性能优化：递归 CTE vs 应用层 BFS

现状：SQLite BFS 在应用层做循环 + 多次 SQL 查询（每跳一次）。

方案：用 SQLite 递归 CTE 一次性完成 BFS 遍历，减少 DB 往返：

-- 单源 BFS 递归 CTE（代替当前逐跳循环）
WITH RECURSIVE bfs(node_id, depth, parent_edge, path) AS (
    -- 初始化：起点
    SELECT source_id, 0, NULL, source_id
    FROM graph_nodes WHERE id = ?
    
    UNION ALL
    
    -- 递归：扩展邻居
    SELECT e.target_id, b.depth + 1, e.id,
           b.path || ' -> ' || e.target_id
    FROM graph_edges e, bfs b
    WHERE e.source_id = b.node_id
      AND b.depth < ?
      AND e.namespace = ?
)
SELECT * FROM bfs ORDER BY depth;

预期效果：N 跳 BFS 从 N 次 SQL 往返减少为 1 次，延迟降低约 50%（在网络 RTT 明显时效果更显著）。

5. 实施计划（E1 子任务分解）

阶段	内容	优先级	复杂度
E1.1	修复 `InMemoryGraph.NavigateBiDir` 伪实现，对齐 SQLite 算法	P1	低
E1.2	SQLite `NavigateBiDir` 无相遇路径时正确处理（返回 unreachable + 最近的可达节点对）	P2	中
E1.3	新增 `extractEntitiesWithNER` 规则 NER，提升实体提取质量	P1	中
E1.4	`Navigate`/`NavigateBiDir` 接口增加 `relationFilter` 参数	P3	低
E1.5	`RecallPipeline` 集成 `ExpandWithSummary`，实现语义 + 图扩展分数融合	P2	中
E1.6	SQLite BFS 升级为递归 CTE 实现（性能优化）	P4	高
E1.7	增加循环检测和路径爆炸防护参数	P3	低

6. 附录

6.1 参考项目速查表

项目	语言	图存储	多跳算法	特点
Graphiti	Python	Neo4j	Cypher BFS	时序记忆、实体关系双模式
Mem0	Python	Neo4j/NetworkX	DFS/BFS	分层记忆、关系类型权重
Letta	Python	SQLite	递归 CTE	持久化、SQL 记忆
Cortex	Python	Neo4j	Neo4j Traversal API	GraphRAG、混合检索
APEX-MEM	多语言	Neo4j	BFS	5维记忆、BM25+向量+图三层融合
Agent_Memory_Techniques	Jupyter	综述	综述	30 种记忆模式对比研究

6.2 当前 NavigateBiDir 降级行为示例

输入：source="n_comfyui", target="n_docker", max_hops=3
期望：如果不连通，返回"无路径" + 告知不连通
实际：返回 n_comfyui 的单向 3 跳邻居 + n_docker 的单向 3 跳邻居（语义错误的降级）

6.3 Recall 链路中 BFS 扩展的位置

Recall 管线：
  1. bge-m3 编码
  2. LanceDB ANN 搜索
  3. bge-reranker 重排  
  4. MMR 多样性去重
  5. [E1 增强] 图谱 BFS 扩展（ExpandWithSummary） ← 这里
  6. 记忆预取（CO_OCCURS > 0.6）
  7. 返回结果 + GraphBFSResult 汇总

6.4 关键代码位置索引

文件	行号	内容
`go/internal/governance/graph_store.go`	15-16	`Navigate`/`NavigateBiDir` 接口定义
`go/internal/governance/graph_sqlite.go`	211-243	SQLite 单源 BFS
`go/internal/governance/graph_sqlite.go`	249-436	SQLite 双向 BFS（含路径重建）
`go/internal/governance/graph_mem.go`	55-94	内存单源 BFS
`go/internal/governance/graph_mem.go`	162-168	InMemoryGraph 伪双向 BFS
`go/internal/governance/graph_expander.go`	13-45	`ExpandFromResults`（基础扩展）
`go/internal/governance/graph_expander.go`	48-99	`ExpandWithSummary`（增强扩展 + 汇总）
`go/internal/storage/recall.go`	58-115	Recall 管线主逻辑
`go/internal/api/routes/graph.go`	71-115	HTTP API 层 navigate 接口
`go/internal/models/memory.go`	101-115	`GraphBFSResult` / `ExpandedRelation` 数据结构

18 KiB Raw Permalink Blame History Unescape Escape

E1 图谱导航 BFS 扩展调研与设计方案

1. 背景与现状分析

1.1 当前 MemoryWeave 图谱导航实现

1.1.1 SQLite 实现（生产级）

1.1.2 内存实现（测试用）

1.1.3 Recall 管线集成（storage/recall.go）

2. 参考项目调研

2.1 Graphiti（Fixie AI）— Agent 时序记忆图谱

2.2 Mem0（mem0ai/mem0）— 分层记忆系统

2.3 Cortex（IASolutionOrg/Cortex）— GraphRAG 知识库

2.4 Letta（letta-ai/letta）— 持久化 Agent 记忆

2.5 APEX-MEM — 多维混合记忆

2.6 NirDiamant/Agent_Memory_Techniques — 方法论综述

3. 现状问题分析

3.1 功能性缺陷

3.2 性能问题

4. 增强设计方案

4.1 修复 InMemoryGraph.NavigateBiDir

4.2 SQLite NavigateBiDir 真正相遇路径查找

4.3 增强实体提取质量

4.4 扩展关系类型过滤

4.5 Recall 管线增强：图扩展与语义结果融合

4.6 循环检测与路径爆炸防护

4.7 性能优化：递归 CTE vs 应用层 BFS

5. 实施计划（E1 子任务分解）

6. 附录

6.1 参考项目速查表

6.2 当前 NavigateBiDir 降级行为示例

6.3 Recall 链路中 BFS 扩展的位置

6.4 关键代码位置索引

18 KiB

Raw Permalink Blame History

1.1.3 Recall 管线集成（`storage/recall.go`）