论文解读 | Can Language Models Solve Graph Problems in Natural Language?

**title:** Can Language Models Solve Graph Problems in Natural Language? **institute:** Xi'an Jiaotong University University of Washington **authors:** Heng Wang , Shangbin Feng , Tianxing He, Zhaoxuan Tan , Xiaochuang Han , Yulia Tsvetkov Date: 2023.5.13 **link:** [2305.10037v1.pdf (arxiv.org)](https://arxiv.org/pdf/2305.10037v1.pdf) # 介绍 本文首次尝试使用大模型来解决图问题。在本文作者基于自然语言提出了含有千余个图基础问题的BenchMark **NLGraph**。作者在GPT3/4上进行实验获得了一些结论。在论文的最后，作者提出了两个可以提升大模型处理图问题的方法。 总结来讲，本文贡献如下： - 提出了首个使用自然语言处理图问题的BenchMark **NLGraph** - 在GPT3/4上进行实验并统计LLM performance，获得了一些规律 - 提出了两个改善方法 # NLGraph 这个BenchMark简单来讲就是一堆用自然语言描述的图并配有其对应的答案。  ## 图生成 生成n个节点，每个节点间有边的概率设置为p。使用n和p来控制图的生成。对于个别的任务有更多的限制因子。 ## 任务 NLGraph包含8种任务 - 联通验证：询问两个点是否联通 - 图中是否存在环 - 拓扑排序 - 最短路 - 最大流 - 二分图匹配 - 哈密尔顿路 - 模拟图神经网络 ## 统计 基础版本包含5902个样例，拓展版本包含29370个样例。 # 实验设置 ## Baseline： 作者使用了多种Prompt作为baseline： - ZERO-SHOT - FEW-SHOT - CoT - 0-CoT - least-to-most (LTM-2023)：将一个大问题拆分成多个子问题逐个击破 - self-consistency (SC-2023)：同一个问题多种问法，最后取最一致的结果 同时作者也将随机作为一种Baseline，例如对于是否的问题，Baseline设置为50%，对于最短路问题将随机选取的路径是否正确作为baseline。 ## Models： TEXT-DAVINCI-003、GPT3/4 # 结论 ## 大模型对图问题有初步的推理能力 - 在联通验证、是否存在环、最短路问题上LLM performance显著高于Random，说明大模型不是随机给的答案，具有初步推理能力。 - 使用COT or COT+SC Prompt的准确率比Random准确率吧高了37.33%-57.82% - 在联通验证、最短路问题上，使用ZERO-SHOT比Random准确率分别高了33.81%和23.33% - 在最短路问题上，COT and COT+SC比Random高了22.81%-62.83% ## 高级Prompt不一定是有益的 - 高级Prompt如CoT，SC在大多数问题上提高了准确率 - 但是在复杂的图问题上，高级Prompt如COT, COT+SC, andLTM的效果反而低于Few-SHOT - 作者认为这种现象的原因是大模型无法生成复杂图问题的思考链 ## 上下文Prompt可能适得其反   - 在复杂图形推理问题上，如哈密尔顿路径和二分图匹配问题上，ZERO-SHOT的效果好于Few-SHOT - 这可能是在复杂问题上，LLM无法从上下文中获得知识，反而会降低注意力 ## LLMs是（不）出奇地脆弱 标题的意思是LLM有可能曲解了问题的推理过程。 尽管LLM的效果很好，但是LLM可能通过利用某些虚假相关性来获得正确答案。举例来讲，由于更高度节点更常被提及且它们更有可能相连，语言模型可能只是计算节点出现次数而非实际查找路径。换言之，在连接性问题上，一些度特别多的点往往是相互连接的，这导致大模型可能人为度多的点就相互连接，而不是通过路径。 于是作者特地设计了两组数据。 ### Chain 将一张图分为k个部分，每个部分是一条独立的链，查询每个链的首节点和尾节点是否相连。首尾虽然是度最小的，但是却相连。 ### Clique 建立k个稠密的独立子图。从不同的子图中选取两个点，由于是稠密图，因此这两个点的度都很高。但是由于独立，这两个点却不相连。 不出意料的，LLM在这两个数据集上的performance下降了40%，证实了作者的猜想。 # 提高Performance的两个方法  ## Build-a-Graph Prompting (BAG) 作者认为将图的文本描述映射到实际概念空间可能会有帮助。因此加了一句“让我们首先构建一个带有节点和边的图” ## Algorithmic Prompting 提示LLM可以使用一些具体的算法解决问题。比如告诉他使用DFS或者BFS来解决这个问题 ## Result 在简单问题上，作者的两个方法可以提高3.07%-16.85% 的Performance。但是对于复杂问题，没有提升。 # 总结 ## 对比论文TALK LIKE A GRAPH： ENCODING GRAPHS FOR LARGE LANGUAGE MODELS 由于《TALK LIKE A GRAPH： ENCODING GRAPHS FOR LARGE LANGUAGE MODELS》在时间上更新，因此在下文简称为后者。而本文称为前者。 ### BenchMark 在BenchMark上两篇文章互补，问题种类上存在交集 ### 在Prompt上 后者相比于前者增加了Encoding部分 在Prompt上两者各有区别，前者有LTM和SC两种Prompt，而后者有Bag prompting (COT-BAG)。不知道为什么后者遗弃了LTM、SC。 ### 在实验上 - 后者增加了模型容量对Performance 的影响 - 后者增加了图的形状的影响 - 在简单图任务上，两者的ZERO-SHOT都好于ZERO-COT - 两人都发现复杂图任务使用高级Prompt会降低LLM Performance - 两者都认为将“图的文本描述映射到实际概念空间可能会有帮助”，前者只是加了一句“Let's construct a graph with the nodes and edges first”，但是后者却真的将LLM在现实问题上进行了实验。 ### 在创新上 - 前者的创新集中在数据集、实验设计、开创性上 - 后者的创新集中在将Encoding纳入变量上 ## Question ### Solve 由于本人是先阅读的后者，因此对前者的工作此前没有了解过，故在后者的解析中提出了几个问题，在此回答一下 - LLM在处理最短路问题上性能如何？其复杂度是否与环问题相同？ - 首先两个任务的性质是不同的，一个是找到正确路径，一个是True/False的问题 - 在本文，最短路和环的难度并不一样。环被划分为基础问题，有三个难度分级。而最短路被划分为进阶问题，有两个难度分级。 ### Generated - 类似于后者，还有哪些变量可以被挖掘出来做实验？ - 语言？ - 点和边的数量上，小图$\rightarrow$大图 - 邻接矩阵表示图 - 树相关的经典问题似乎没有提及到 - 最小生成树 - 树的直径 - ... - Tuning/Lora