PathRAG通过图剪枝的方法优化Graph-based-RAG的性能方法浅析
PathRAG：通过图剪枝的方法优化Graph-based RAG的性能方法浅析
PathRAG 也是一种新型 Graph-based RAG 方法，通过检索索引图中的关键关系路径，减少噪声并优化 LLM 提示。其核心创新在于基于流的剪枝算法和路径为基础的提示策略，特别适用于捕捉复杂数据集中的关系。（其实可以看做 相比GraphRAG假如剪枝算法和路径提示策略，减少噪声并提升性能 ）
三种Graph-based RAG对比总结（PathRAG、GraphRAG、LightRAG）：
• PathRAG ：通过从索引图中检索关键的关系路径来减少冗余信息。PathRAG使用基于流的剪枝算法来识别和提取最相关的路径，从而减少噪声并提高生成答案的质量。(专注于关系路径的检索，通过流式剪枝算法识别最可靠的关系路径，并将这些路径转换为文本形式用于提示生成模型。这种方法能够更好地捕捉节点之间的关系。)
• GraphRAG ：通常通过社区检测算法对图进行分割，并从子社区中逐步聚合信息。这种方法可能会包含大量冗余信息，因为其使用了所有相关社区的信息。(主要依赖于社区检测和信息聚合，可能无法有效利用复杂的关系路径。)
• LightRAG ：采用双阶段检索框架，从局部和全局级别检索相关信息。虽然这种方法提高了检索效率，但仍然可能包含不必要的信息。(虽然也使用图结构，但其检索过程更侧重于快速检索，可能没有深入探索关系路径的潜力。)
下面再来看看PathRAG的方法。
PathRAG方法
PathRAG 的方法论分为三个阶段，具体如下：
1. 节点检索
从用户查询
q q
q 中使用 LLM 提取关键词，记为
K q K_q
K
q
。
通过密集向量匹配（使用余弦相似度）检索相关节点，将节点和关键词编码为嵌入
X V X_V
X
V
和
X q X_q
X
q
。
检索
N N
N 个相关节点，
N N
N 可选值包括 {10, 20, 30, 40, 50, 60}，结果子集为
V q ⊆ V V_q \subseteq V
V
q
⊆
V ，其中
V V
V 是索引图的节点集。
2. 路径检索
使用基于流的剪枝算法，从
V q V_q
V
q
中的节点对
v start , v end v_{\text{start}}, v_{\text{end}}
v
start
,
v
end
提取关键关系路径，考虑距离感知。
资源传播公式为：
S ( v i )
∑ v j ∈ N ( ⋅ , v i ) α ⋅ S ( v j ) ∣ N ( v j , ⋅ ) ∣ S(v_i) = \sum_{v_j \in N(\cdot, v_i)} \frac{\alpha \cdot S(v_j)}{|N(v_j, \cdot)|}
S
(
v
i
)
=
v
j
∈
N
(
⋅
,
v
i
)
∑
∣
N
(
v
j
,
⋅
)
∣
α
⋅
S
(
v
j
)
其中
α \alpha
α 是衰减率，可选值包括 {0.6, 0.7, 0.8, 0.9, 1.0}；
N ( v i , ⋅ ) N(v_i, \cdot)
N
(
v
i
,
⋅
) 和
N ( ⋅ , v i ) N(\cdot, v_i)
N
(
⋅
,
v
i
) 分别是指向和来自
v i v_i
v
i
的邻居节点集。
引入早期停止策略，当
S ( v i ) ∣ N ( v i , ⋅ ) ∣ < θ \frac{S(v_i)}{|N(v_i, \cdot)|} < \theta
∣
N
(
v
i
,
⋅
)
∣
S
(
v
i
)
<
θ 时停止，实验中
θ
0.05 \theta = 0.05
θ
=
0.05 。
路径可靠性计算为：
S ( P )
1 ∣ E P ∣ ∑ v i ∈ V P S ( v i ) S(P) = \frac{1}{|E_P|} \sum_{v_i \in V_P} S(v_i)
S
(
P
)
=
∣
E
P
∣
1
v
i
∈
V
P
∑
S
(
v
i
)
其中
∣ E P ∣ |E_P|
∣
E
P
∣ 是路径
P P
P 中的边数，
V P , E P V_P, E_P
V
P
,
E
P
分别是路径中的节点和边集。
按可靠性
S ( P ) S(P)
S
(
P
) 排序，保留前
K K
K 个路径，
K K
K 可选值包括 {5, 10, 15, 20, 25}。
算法复杂度为
O ( N 2 ( 1 − α ) θ ) O(\frac{N^2}{(1-\alpha)\theta})
O
(
(
1
−
α
)
θ
N
2
) ，其中
N ≤ 60 N \leq 60
N
≤
60 ，索引图节点数
∣ V ∣ ∼ 1 0 4 |V| \sim 10^4
∣
V
∣
∼
1
0
4 ，计算效率较高。
3. 答案生成
将选定路径转化为文本形式，路径文本通过连接节点和边块生成：
t P
concat ( [ ⋯ ; t v i ; t e i ; t v i + 1 ; ⋯ ] ) t_P = \text{concat}([\cdots; t_{v_i}; t_{e_i}; t_{v_{i+1}}; \cdots])
t
P
=
concat
([
⋯
;
t
v
i
;
t
e
i
;
t
v
i
1
;
⋯
])
按可靠性升序排列路径，提示为：
这种排序策略解决了“中间丢失”问题，确保 LLM 关注最相关信息（LLM使用 “GPT-4o-mini” 作为所有 LLM 组件，索引图与 GraphRAG相同。）。
实验结果
参考文献：PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths，https://arXiv.org/abs/2502.14902)
code：https://github.com/BUPT-GAMMA/PathRAG