图灵对话：为大型语言模型编码图结构

想象一下你周围的所有事物——你的朋友、厨房用具甚至自行车零件——它们都以不同方式相互连接。在计算机科学中，“图”这个术语用于描述对象之间的连接关系。图由节点（对象本身）和边（连接两个节点的关系）组成。如今图结构无处不在：互联网本身就是由相互链接的网站构成的巨型图，就连搜索引擎使用的知识也是以图的形式组织的。

人工智能领域取得了显著进展——例如能在几秒钟内编写故事的聊天机器人，甚至能解读医疗报告的软件。这些令人兴奋的进步主要归功于大型语言模型（LLM）。针对不同用途的新LLM技术正在不断开发中。

鉴于图的普遍存在和LLM技术的兴起，我们在ICLR 2024上发表的论文《图灵对话：为大型语言模型编码图结构》提出了一种方法，旨在教导强大的LLM如何更好地进行图信息推理。图是组织信息的有用方式，但LLM主要是在常规文本上训练的。我们的目标是测试不同技术以找出最有效的方法并获得实践见解。

将图转换为LLM能理解的文本是一项极其复杂的任务。这种困难源于图结构固有的复杂性，包括多个节点和连接它们的复杂边网络。我们的工作研究如何将图转换为LLM能理解的格式，并设计了名为GraphQA的基准测试，用于研究不同方法在不同图推理问题上的表现，同时展示了如何以使LLM能够解决图问题的方式表述图相关任务。

我们发现LLM在图推理任务上的表现受三个基本层面影响：

图编码方法
图任务本身的性质
有趣的是，所考虑图的具体结构

这些发现为我们如何最佳地表示图以供LLM使用提供了线索。选择正确的方法可以使LLM在图任务上的表现提升高达60%！

将图表示为文本

为了系统性地找出将图转换为文本的最佳方法，我们首先设计了名为GraphQA的基准测试。可以将GraphQA视为专门评估强大LLM在图特定问题上表现的考试。我们想了解LLM在不同设置下理解和解决涉及图的问题的能力。

为了为LLM创建全面而现实的考试，我们不只使用一种图类型，而是使用混合图类型确保连接数量的广度。这主要是因为不同的图类型会使解决此类问题变得更容易或更困难。通过这种方式，GraphQA可以帮助暴露LLM思考图时的偏见，使整个考试更接近LLM在现实世界中可能遇到的情况。

GraphQA专注于与图相关的简单任务，例如检查边是否存在、计算节点或边的数量、查找与特定节点连接的节点以及检查图中是否存在环。这些任务可能看起来基础，但它们需要理解节点和边之间的关系。通过涵盖从识别模式到创建新连接的不同类型挑战，GraphQA帮助模型学习如何有效分析图。这些基本任务对于图上更复杂的推理（如查找节点间最短路径、检测社区或识别有影响力的节点）至关重要。

此外，GraphQA包括使用各种算法生成随机图，如Erdős-Rényi、无标度网络、Barabasi-Albert模型和随机块模型，以及更简单的图结构，如路径、完全图和星形图，为训练提供多样化的数据集。

在处理图时，我们还需要找到能让LLM理解图相关问题的方法。提示启发法是实现这一目标的不同策略。让我们分解常见的几种：

零样本：简单描述任务（“这个图中有环吗？”）并让LLM直接尝试。不提供示例。
少样本：这就像在正式考试前给LLM一个迷你练习测试。我们提供几个图问题示例及其正确答案。
思维链：在这里，我们通过示例向LLM展示如何逐步分解问题。目标是教导它在面对新图时生成自己的“思维过程”。
零样本思维链：与CoT类似，但我们不给训练示例，而是给LLM一个简单提示，如“让我们逐步思考”，以触发它自己的问题解决分解。
构建图：这专门用于图任务。我们在描述中添加短语“让我们构建一个图…”，帮助LLM专注于图结构。

我们探索了将图转换为LLM能处理的文本的不同方法。我们的关键问题是：

节点编码：如何表示单个节点？测试的选项包括简单整数、常见名称（人物、角色）和字母。
边编码：如何描述节点之间的关系？方法涉及括号表示法、如“是朋友”的短语和箭头等符号表示。

各种节点和边编码被系统性地组合。这导致了如下图所示的功能：

分析与结果

我们进行了三个关键实验：一个测试LLM如何处理图任务，另外两个理解LLM大小和不同图形状如何影响性能。我们在GraphQA上运行所有实验。

LLM如何处理图任务

在这个实验中，我们测试了预训练LLM在解决图问题（如识别连接、环和节点度）上的表现。以下是我们学到的：

LLM表现挣扎：在大多数这些基本任务上，LLM的表现并不比随机猜测好多少。
编码至关重要：我们如何将图表示为文本对LLM性能有很大影响。“关联”编码在大多数任务中总体表现优异。

更大通常更好

在这个实验中，我们想看看LLM的大小（就参数数量而言）是否影响它们处理图问题的能力。为此，我们在PaLM 2的XXS、XS、S和L尺寸上测试了相同的图任务。以下是我们发现的总结：

通常，更大的模型在图推理任务上表现更好。似乎额外的参数为它们提供了学习更复杂模式的空间。
奇怪的是，大小对于“边存在”任务（找出图中两个节点是否连接）并不那么重要。
即使最大的LLM也无法在环检查问题（找出图是否包含环）上持续击败简单的基线解决方案。这表明LLM在某些图任务上仍有改进空间。

不同的图形状会混淆LLM吗？

我们想知道图的“形状”（节点如何连接）是否影响LLM在其上解决问题的能力。我们发现图结构对LLM性能有很大影响。例如，在询问是否存在环的任务中，LLM在紧密互连的图（环在那里很常见）上表现出色，但在路径图（环从不发生）上表现挣扎。有趣的是，提供一些混合示例有助于它适应。例如，对于环检查，我们在提示中添加了一些包含环和一些没有环的示例作为少样本示例。其他任务也出现了类似模式。

结论

简而言之，我们深入研究了如何最佳地将图表示为文本以便LLM理解。我们发现了三个重要的影响因素：

如何将图转换为文本：我们如何将图表示为文本显著影响LLM性能。关联编码在大多数任务中总体表现优异。
任务类型：某些类型的图问题对LLM来说往往更难，即使有良好的图到文本转换。
图结构：令人惊讶的是，我们进行推理的图的“形状”（连接密集、稀疏等）影响LLM的表现。

这项研究揭示了如何为LLM准备图数据的关键见解。正确的编码技术可以显著提高LLM在图问题上的准确性（改善范围从约5%到超过60%）。我们的新基准测试GraphQA将有助于推动该领域的进一步研究。