图灵对话：大语言模型的图结构编码技术解析

想象你周围的一切——朋友、厨房工具甚至自行车零件——它们都以不同方式相互连接。在计算机科学中，“图”（graph）被用来描述对象间的连接关系。图由节点（对象本身）和边（节点间的连接，表示关系）组成。图无处不在：互联网本身就是由网站链接构成的巨型图，甚至搜索引擎使用的知识也以图的形式组织。

人工智能的显著进步（如能秒写故事的聊天机器人、解读医疗报告的软件）主要归功于大语言模型（LLM）。随着图的普及和LLM技术的发展，我们在ICLR 2024发表的论文《Talk like a Graph: Encoding Graphs for Large Language Models》中提出了一种方法，旨在教会强大的LLM如何更好地进行图信息推理。图是组织信息的有用方式，但LLM主要基于常规文本训练。目标是通过测试不同技术找到最优方案并获得实践洞察。

将图转换为LLM可理解的文本是一项极其复杂的任务，难度源于图结构的内在复杂性（多节点和复杂的边连接网络）。我们的工作研究如何将图转换为LLM可理解的格式，并设计了名为GraphQA的基准测试，用于研究不同方法在各种图推理问题上的表现，同时展示如何以LLM可解决的方式表述图相关问题。实验表明，LLM在图推理任务上的性能受三个基本因素影响：1）图编码方法，2）图任务本身的性质，3）有趣的是，图的具体结构。这些发现为如何最佳表示图提供了线索，选择正确的方法可使LLM在图任务上的性能提升高达60%！

图作为文本

为了系统性地找出将图转换为文本的最佳方式，我们首先设计了GraphQA基准测试。GraphQA如同一个考试，专门评估强大LLM在图特定问题上的表现。我们希望通过不同设置考察LLM理解和解决图相关问题的能力。为创建全面且真实的测试，我们使用多种图类型（确保连接数的广度），因为不同图类型会使问题解决难度不同。这有助于暴露LLM在图思考中的偏见，并使测试更接近现实场景。

GraphQA专注于图相关简单任务，如检查边是否存在、计算节点或边数、查找与特定节点连接的节点以及检查图中的环。这些任务看似基础，但需要理解节点和边的关系。通过涵盖从识别模式到创建新连接的各种挑战，GraphQA帮助模型学习有效分析图。这些基本任务对更复杂的图推理（如查找节点间最短路径、检测社区或识别有影响力节点）至关重要。此外，GraphQA包括使用多种算法（如Erdős-Rényi、无标度网络、Barabasi-Albert模型和随机块模型）生成随机图，以及更简单的图结构（如路径、完全图和星形图），为训练提供多样化数据。

处理图时，我们还需找到向LLM提问图相关问题的策略。提示启发式（prompting heuristics）是不同策略的总结：

零样本（Zero-shot）：简单描述任务（“图中是否有环？"）并让LLM直接执行，不提供示例。
少样本（Few-shot）：在正式测试前提供少量示例问题及其正确答案，如同迷你练习测试。
思维链（Chain-of-Thought）：通过示例展示如何逐步分解问题，旨在教会LLM面对新图时生成自己的"思考过程”。
零样本思维链（Zero-CoT）：类似于CoT，但不提供训练示例，而是给出简单提示（如"让我们逐步思考"）以触发其自主问题分解。
构建图（BAG）：专门针对图任务，在描述中添加"让我们构建图…“短语，帮助LLM聚焦图结构。

我们探索了将图转换为LLM可处理文本的不同方式，关键问题包括：

节点编码：如何表示单个节点？测试选项包括简单整数、常见名称（人物、角色）和字母。
边编码：如何描述节点间关系？方法涉及括号表示法、短语（如"是朋友”）和符号表示（如箭头）。通过系统组合不同节点和边编码，我们得到了多种编码函数（见下图示例）。

分析与结果

我们进行了三个关键实验：一个测试LLM处理图任务的能力，另两个理解LLM规模和不同图形状对性能的影响。所有实验均在GraphQA上运行。

LLM如何处理图任务

本实验中，我们测试了预训练LLM在识别连接、环和节点度等图问题上的表现。主要发现：

LLM表现挣扎：在大多数基础任务上，LLM的表现仅略优于随机猜测。
编码至关重要：图作为文本的表示方式对LLM性能影响巨大，“关联”（incident）编码在多数任务中表现优异。结果总结见下图。

更大通常更好

本实验旨在观察LLM规模（参数数量）是否影响其处理图问题的能力。我们测试了PaLM 2的XXS、XS、S和L尺寸在同一图任务上的表现。总结如下：

通常，更大模型在图推理任务上表现更好，额外参数似乎为其学习复杂模式提供了空间。
奇怪的是，规模对"边存在"任务（判断两节点是否连接）影响较小。
即使最大LLM也无法在环检查问题（判断图是否含环）上持续击败简单基线方案，表明LLM在某些图任务上仍有改进空间。

不同图形状会混淆LLM吗？

我们探究图的"形状"（节点连接方式）是否影响LLM解决问题的能力。下图展示了不同图形状示例。

我们发现图结构对LLM性能影响巨大。例如，在询问是否存在环的任务中，LLM在紧密互连的图上表现优异（环常见），但在路径图上挣扎（从无环）。有趣的是，提供混合示例有助于适应：例如，对于环检查，我们在提示中添加含环和不含环的少样本示例。其他任务也出现类似模式。

结论

总之，我们深入研究了如何最佳地将图表示为文本以供LLM理解。发现三大关键因素：

图到文本的转换方式：图的文本表示显著影响LLM性能，“关联"编码在多数任务中表现优异。
任务类型：某些图问题即使经过良好转换，对LLM仍较难。
图结构：出乎意料地，推理所用图的"形状”（连接密集度、稀疏度等）影响LLM表现。

本研究揭示了如何为LLM准备图的关键见解。正确的编码技术可显著提升LLM在图问题上的准确率（改善幅度约5%至60%以上）。我们的新基准GraphQA将推动该领域的进一步研究。

致谢

我们感谢合著者Jonathan Halcrow的宝贵贡献，同时衷心感谢Anton Tsitsulin、Dustin Zelle、Silvio Lattanzi、Vahab Mirrokni及Google Research图挖掘团队的深刻评论、仔细校对和建设性反馈，极大提升了工作质量。特别感谢Tom Small为本帖创建动画。