通过消除边来扩展知识图谱

我们如何改变数据模型以改变添加节点的复杂度类别，同时实现更快的遍历。

译自 Scaling Knowledge Graphs by Eliminating Edges，作者 Ben Chambers。

知识图谱能够以补充向量相似性的方式链接相关内容。就像超链接允许将网站与相关信息连接起来一样，图中的边能够将内容与其他相关但并不一定相似的内容连接起来。

通常，这为生成式 AI 应用程序提供了更完整的上下文参考，从而产生更完整的答案。与其拥有 10 个最相关信息的近似副本，不如拥有一个副本和 9 个提供更多主题深度和广度的相关信息。

我们最近引入了以内容为中心的知识图谱作为更适合生成式 AI 和图检索增强生成 (RAG) 的方法。从那时起，我们为 LangChain 贡献了 GraphVectorStore 并引入了多种推断内容之间链接的技术，包括 HTML 中的显式链接、使用 Keybert 的常用关键词、使用 GLiNER 的命名实体提取以及文档和标题的层次结构。

其中一些技术会导致高度连接的知识图谱。例如，使用常用关键词链接节点将在应用于相同主题的文档时创建高度连接的块集群。

在最坏的情况下，如果每个节点都有相同的五个关键词，那么我们将在节点之间创建 5 * n * (n - 1) 条边。由于边是在加载数据时创建的，这会导致加载节点所花费的时间呈二次方增长——每个新节点都必须与所有过去的节点链接！

在这里，我们将讨论我们如何改变数据模型来改变添加节点的复杂度类别，同时实现更快的遍历。关键变化是存储出站和入站链接，而不是具体化边。

在关键词示例中，这使我们能够持久化 5 个入站和出站链接，而不是 5 * (n - 1) 条边，确保在添加新节点时不会出现性能下降。这需要对遍历进行更改，以便在查询时发现边，而不是在加载节点时发现边。正如我们将看到的，有一些方法可以利用这一点来实现更快的遍历。

以内容为中心的知识图谱

以内容为中心的知识图谱是节点代表内容的知识图谱——例如文本段落、图像和表格。这些特别适合捕获多模态信息，并且比更详细的以实体为中心的知识图谱更容易构建。内容之间的关系——段落之间的链接、段落引用的图像——能够检索更完整的大型语言模型 (LLM) 上下文。

使用内容作为节点与 GenAI 生态系统很好地契合——LangChain 文档成为一个节点。我们已经讨论了多种在这些节点之间引入边的方法：例如，HTML 中的显式链接、常用关键词和交叉引用。提取文档之间链接的能力对于构建这些知识图谱至关重要。根据节点之间链接的密度，使用具体化边的原始实现会遇到扩展问题。

链接和边

为了提高以内容为中心的知识图谱的兼容性，我们希望描述边，而无需任何超出每个文档元数据的额外信息。与其专门描述边（这将是不可能的，因为它涉及两个不同的文档），我们改为使用“链接”的概念。每个文档定义零个或多个链接，这些链接连接到其他文档上的相应链接。

具有出站链接的节点与具有匹配入站链接的每个节点都有边。

在下面的示例中，我们看到了三个节点。所有三个节点都通过一个共同的关键字“foo”链接在一起。节点 2 是唯一一个包含关键字“bar”的节点，因此它没有该类型/标签的边。节点 1 有一条指向“bar”的出边，节点 3 有一条入边，因此它们通过一条有向边连接。

类似于超图可以表示为二部图的方式，上述内容可以可视化为一个图，其中节点之间的边通过表示标签的不同类型的节点传递。在这种情况下，出边是从节点到标签的边，入边是从标签到节点的边。原始图中节点之间的边与该二部图中通过标签节点的长度为 2 的路径相同。

问题：共同关键字和高度连接的图

关键字是双刃剑。它们可以用来将具有共享关键字的节点链接在一起，以从节点中检索扩展特定主题的信息。但是，当关键字重叠过多时，它会迅速退化为一个完全连接的图，节点对之间存在边。使用 TF-IDF（词频-逆文档频率）等技术来选择跨文档更独特的关键字可以有所帮助，但理想情况下，即使连接度很高，知识图的性能也不会下降。

解决方案：避免物化边

与其在添加节点时通过显式物化边来链接节点，我们可以查询连接并在遍历图时查询连接。

	物化边	基于查询的边
加载	查询并写入所有边。`O(t*n^2)` 用于写入具有 `t` 个标签的 `n` 个完全连接的节点。`O(n)` 如果没有连接。	写入每个节点的入边和出边。`O(t*n)` 用于写入 `n` 个节点（无论是否连接）。
遍历	`O(1)` 查询每个源节点。`O(n)` 查询以查找从 n 个源节点可达的所有节点。	`O(t)` 查询每个源节点。`O(T)`（唯一标签的数量）以查找所有可达的节点。

加载

这里的主要变化是，我们不再存储以源为键的边，而是存储以标签为键的入边标签。这使我们能够请求从给定节点发出的边的所有目标。

遍历

在遍历期间更改为查询连接意味着查找给定源节点的目标需要对每个出边标签进行单独的查询。但是，由于以下几个原因，这不会降低性能：

该实现能够并行查询每个标签的链接节点。使用像 DataStax Astra DB/ Apache Cassandra 这样的高度可扩展数据库使并发成为一种可行的技术。
我们对目标文本嵌入进行反规范化，以便每个查询都可以针对与查询最相似的顶级目标节点进行。这使我们能够将查询限制为每个出边标签要考虑的最佳节点，而不是获取所有节点。
我们可以记住我们已经处理过的出边标签。在高度连接（常见）标签的情况下，一旦我们检索到具有给定关键字的入边的节点集，我们就不需要再这样做——即使还有其他边指向该节点，结果也是一样的（到达该目标）。这使遍历能够比必须遍历边的情况更早地切断。从本质上讲，我们利用了二部图，并记住了已访问的内容节点和已访问的标签节点。

事实上，正如您将在基准测试中看到的那样，我们发现以这种方式遍历标签实际上比遍历边更快。在通用数据库之上构建用于互连内容使我们能够优化模式和查询模式以进行检索。在这种情况下，它使我们能够在遍历期间考虑连接节点的每个标签一次（到达的节点集不会改变），而传统的图则需要考虑节点之间的每条边。

用例：来自 PDF 的关键字链接

为了演示关键字的使用，我们展示了如何加载 PDF，将其拆分为块，并使用 Keybert 为每个块提取关键字。

from langchain_openai import OpenAIEmbeddings
import cassio
from langchain_community.graph_vectorstores.cassandra import (
CassandraGraphVectorStore,
)
from langchain_community.graph_vectorstores.extractors import (
    LinkExtractorTransformer,
    KeybertLinkExtractor,
)
from langchain_community.document_loaders import PyPDFLoader
from langchain_text_splitters import RecursiveCharacterTextSplitter

# Initialize AstraDB / Cassandra connections.
cassio.init(auto=True)

# Create a GraphVectorStore, combining Vector nodes and Graph edges.
knowledge_store = CassandraGraphVectorStore(OpenAIEmbeddings())

# Load and split content as normal.
text_splitter = RecursiveCharacterTextSplitter(
    chunk_size=1024,
    chunk_overlap=64,
    length_function=len,
    is_separator_regex=False,
)
loader = PyPDFLoader("Tourbook.pdf")
pages = loader.load_and_split(text_splitter)

# Create a document transformer extracting keywords.
transformer = LinkExtractorTransformer([
    KeybertLinkExtractor(extract_keywords_kwargs={
      "stop_words": "english",
    }),
])

# Apply the document transformer.
pages = transformer.transform_documents(pages)

# Store the pages in the knowledge store.
knowledge_store.add_documents(pages)

基准测试结果

关于印度旅行的 PDF 文档被拆分为 136 个块，并六次加载到以内容为中心的知识图中。每次加载都会创建 136 个新块。使用旧方法（物化边），我们看到加载文档的时间从一开始就很高，并且大致呈线性增长；每个新文档都必须与所有旧文档链接，这些文档会随着时间的推移而增加。因此，加载所有文档的总时间是指数级的。使用新方法（按需边），时间是恒定的，并且通常要低得多，因为没有创建边。

我们还发现，在这两种情况下，遍历图以检索文档所花费的时间大致相同——相对恒定。

试试看！

以内容为中心的知识图谱与向量存储一样快速且易于填充。通过存储有关每个 Document 链接到的内容的信息，可以可扩展且高效地存储具有任意高连接性的图。由最大边际相关性引导的遍历允许遍历图以检索与查询最相关和最多样化的信息（以及与该信息链接的相关信息）。

要体验这些进步带来的好处，请尝试 langchain-core 0.2.23 和 langchain-community 0.2.10 中的最新改进。我们邀请您使用 LangChain 将以内容为中心的知识图谱集成到您的项目中，并探索连接和检索内容的进一步增强。分享您的反馈并加入我们，共同改进这些工具，以突破人工智能中知识图谱的可能性边界。