01.
前言
Comparision between Direct LLM, RAG, and GraphRAG.
02.
理论
query 复杂度有限性
Normal query vs. Weird query
正常的query："爱因斯坦获得诺贝尔奖的时间是哪一年？"
In which year did Einstein win the Nobel Prize?
知识图谱中的查询路径：
找到节点“爱因斯坦”。 跳转到与“爱因斯坦”相关的“诺贝尔奖”节点。 返回奖项颁发的年份信息。 跳数：2 跳
说明：这是一个常见的用户问题，用户想要知道的是与某个具体实体直接相关的单一事实。知识图谱在这种情况下只需要进行少量跳数的查询即可完成任务，因为所有相关信息都直接与爱因斯坦这个中心节点关联。这种查询在实际应用中非常普遍，例如查询名人背景信息、奖项历史、事件时间等。
古怪的query："相对论的发现者获得诺贝尔奖的年份与他们在一个以银行保密法和阿尔卑斯山壮丽风景而闻名的国家发明的专利数量之间有什么关系？"
What is the relationship between the year the discoverer of the theory of relativity received the Nobel Prize and the number of patents they invented in a country famous for its bank secrecy laws and the magnificent scenery of the Alps?
知识图谱中的查询路径：
找到“相对论”的“发明者”是“爱因斯坦”。 跳转到与“爱因斯坦”相关的“诺贝尔奖”节点。 查找“诺贝尔奖”获奖年份。 通过“银行保密法和阿尔卑斯山”找到“瑞士” 跳转到与“爱因斯坦”相关的“专利”节点。 查找与瑞士期间相关的专利信息。 比较专利数量和获奖年份之间的关系。 跳数：7跳
说明：这个问题较为复杂，要求不仅仅是查询单一的事实，还涉及多个节点之间的复杂关联。这种问题在实际场景中不太常见，因为用户一般不倾向于在一次查询中寻求如此复杂的信息交叉。通常，这类问题会被分解为多个简单查询，以便逐步获取信息。
“捷径”的局部 dense 结构
知识图谱中是一个存在一些局部 dense 结构，对于有些 query，有一些“捷径”，可以从一个 entity 通过捷径快速连接到多跳之外的 entity。
"Shortcuts" structure
假设我们有一个家庭关系的知识图谱，包含以下实体和关系：
Alex 是 Brian 的孩子 ( Alex - child_of - Brian)Cole 嫁给了 Brian ( Cole - married_to - Brian)Daniel 是 Cole 的哥哥 ( Daniel - brother_of - Cole)Daniel 是 Alex 的舅舅 ( Daniel - uncle_of - Alex)这是一个包含冗余信息的密集型的知识图谱。显然，可以通过前三条 relationships 推导出最后一条 relationship。但知识图谱中往往存在一些这种冗余信息的捷径。这些捷径可以减少一些 entities 之间的跳数。
路由的起点，可以通过向量相似性查找来完成。可以涉及到 query 与 entities 或 query 与 relationships 的相似度关系查找。 从起点找到其它信息的路由过程，可以用一个 LLM 来代替完成。将这些备选信息放进 prompt 里，依托 LLM 强大的自注意力机制来挑选有价值的路由。由于 prompt 长度有限，所以只能将局部知识图谱的信息放入，比如起点附近限定跳数内的知识图谱信息，这一点是正好可以由跳数有限性来保证。
03.
方法概览
Overall pipeline of our method
04.
方法详解
4.1. 向量入库
(Alex, child of, Brian) -> "Alex child of Brian"
(Cole, married to, Brian) -> "Cole married to Bria"
4.2. 向量相似搜索
对于输入的 Query，我们遵循常见的 GraphRAG 中的范式（如HippoRAG，MS GraphRAG），将 query 提取 entities，对于每个 query entity，转换成 embedding，分别对 entity collection 进行 vector similarity search。然后将所有 query entities搜索得到的结果进行合并。 对于 relationship 的向量搜索，我们直接将 query string，转换成 embedding，对 relationship collection 进行 vector similarity search。
4.3. 扩展子图
Expanding subgraph from two retrieved ways, then merged them together
对于起始 relationships，我们往外扩大一定跳数，得到
我们将两个 set 取并集，
基于跳数有限性，我们仅需要扩大较小的度数（如1，2等），就能涵盖大部分可能有助回答的 relationships。请注意，这一步扩展的度数的概念和回答问题总共需要的跳度的概念不同。比如，如果回答一个 query 问题涉及两个相差 n 跳的 entities，那么实际上往往只需要扩展 ⌈n / 2⌉ 度就可以，因为这两个 entities 是被向量相似召回后的两个起始端点。如图，向量召回到了两个红色的 entities，只需要从它们开始，相向扩展 2 度，就能覆盖到 4 度的跳数，这足以回答涉及到这两个 entities 的 4 跳问题。
In fact, to answer the question with 4 degree hops, you only need to expand it by 2 degrees from both end points in the setting.
4.4. LLM Rerank
One shot input prompt
I will provide you with a list of relationship descriptions. Your task is to select 3 relationships that may be useful to answer the given question. Please return a JSON object containing your thought process and a list of the selected relationships in order of their relevance.
**Question:**
When was the mother of the leader of the Third Crusade born?
**Relationship descriptions:**
[1] Eleanor was born in 1122.
[2] Eleanor married King Louis VII of France.
[3] Eleanor was the Duchess of Aquitaine.
[4] Eleanor participated in the Second Crusade.
[5] Eleanor had eight children.
[6] Eleanor was married to Henry II of England.
[7] Eleanor was the mother of Richard the Lionheart.
[8] Richard the Lionheart was the King of England.
[9] Henry II was the father of Richard the Lionheart.
[10] Henry II was the King of England.
[11] Richard the Lionheart led the Third Crusade.
One shot input prompt
{
"thought_process": "To answer the question about the birth of the mother of the leader of the Third Crusade, I first need to identify who led the Third Crusade and then determine who his mother was. After identifying his mother, I can look for the relationship that mentions her birth.",
"useful_relationships": [
"[11] Richard the Lionheart led the Third Crusade",
"[7] Eleanor was the mother of Richard the Lionheart",
"[1] Eleanor was born in 1122"
]
}
这个 prompt 是一个展示的参考，实际上，如何把 relationships 中的三元组转成一个通顺的短句，是一个棘手的问题。但是，你完全可以用上文提到的启发性的方法，把三元组直接拼在一起。如：
(Eleanor, born in, 1122) 可以直接转成 Eleanor born in 1122
这种方式有时会带来一定的语法问题，但它是最快，最直接的方式，也不会对 LLM 带来误解。
4.5. 获得最终 passages
对于上面的例子，实际上可以在 LLM rerank 这个阶段直接返回最终的回答，比如在 One shot output prompt 的 json 字段里加上比如 “final answer”的字段。但是，这一步的 prompt 里只有 relationship 的信息，不一定所有问题都可以在这个阶段返回最终答案，所以其它具体的信息应该要在原始的 passsage 里获得。
LLM 返回精确排序后的 relationships。我们只需要取出先前在存储中的对应 relationship 信息，从中获取相应的 metadata，在那里有对应的 passage ids。这些 passages 信息就是最终被 retrieved 到的 passages。后续生成回答的过程和 naive RAG 一样，就是将它们放入 prompt 的 context 中，让 LLM 给出最后的回答。
05.
结果
我们使用与 HippoRAG 中一致的 dense embedding，facebook/contriever，来作为我们的 embedding 模型，可以看到，在三个 multi-hop 的数据集上结果比较上，我们的方法大幅超过 naive RAG 和 HippoRAG 的结果。所有的方法使用相同的 embedding 模型设置。我们使用 Recall@2 作为我们的衡量指标，它表示，
Recall（召回率） = 检索到的相关文档总数/数据存储中相关文档总数
On the multi-hop datasets, our method outperforms naive RAG and HippoRAG in all datasets, all of them are compared using the same facebook/contriever embedding model.
作者介绍
张晨
Zilliz 算法工程师
推荐阅读
