Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?¶
会议: ACL 2025
arXiv: 2402.07140
代码: 无
领域: LLM/NLP
关键词: 图推理, 图描述顺序, Prompt Engineering, BFS/DFS, PageRank, 图问题
一句话总结¶
首次系统研究了图描述顺序（BFS、DFS、PageRank、PPR）对LLM解决图推理问题的影响，发现有序描述显著优于随机描述，且不同任务偏好不同的排列策略。
研究背景与动机¶
- LLM在推理任务（数学推理、逻辑推演）上取得显著进展，图问题因其结构复杂性成为重要研究方向。
- 已有工作探索了不同的图编码方法（邻接矩阵、边列表等）和精心设计的prompt，但普遍忽略了一个关键因素：图描述中边/节点的呈现顺序。
- 图本身没有固定的文本表示，边的排列顺序可能影响模型的注意力分配，从而影响推理过程。
- 以往研究默认使用随机顺序描述图结构，从未系统考察顺序的影响。
- 不同的描述顺序可能为模型提供不同的"视角"——BFS提供层级视角、DFS提供深度视角、PageRank提供全局重要性视角。
- 本文首次提出"图描述顺序"这一研究问题，并构建了GraphDO数据集进行全面实验，填补了该领域空白。
方法详解¶
整体框架¶
将图问题建模为一个优化问题：给定图 \(\mathcal{G}=(\mathcal{V},\mathcal{E})\)，寻找最优描述顺序 \(o \in \mathcal{O}\)，使LLM在图任务上的评分最大化。框架包含三个模块：图编码器（将图转为文本）、图描述排序（决定边的呈现顺序）、任务提问（生成对应图任务的问题）。采用邻接格式（edge list）作为统一编码方式。
模块一：图描述排序策略¶
设计了四种有序描述（对比随机baseline）：
- BFS顺序：从随机根节点出发，逐层遍历，在对偶图 \(\mathcal{G}^*\) 上执行以确保所有边被包含。提供层级化的图结构视角。
- DFS顺序：从根节点出发递归深入探索后回溯，提供深度优先的路径视角。
- PageRank顺序：按节点PageRank得分降序排列，\(PR(v) = \alpha \sum_{u} \frac{PR(u)}{|\mathcal{N}(u)|} + (1-\alpha)\)（\(\alpha=0.85\)），提供全局节点重要性视角。
- Personalized PageRank顺序：引入个性化向量 \(e_v\)（与任务相关的目标节点），提供局部化的重要性视角。
模块二：图任务设计¶
涵盖六类图推理任务，覆盖不同复杂度层级：
- 局部推理：连通性检测(T1)、环检测(T2)——二分类任务
- 全局推理：哈密顿路径(T3)、最短路径(T4)、拓扑排序(T5)——需要全局图结构理解
- 属性学习：节点分类(T6)——基于邻居标签预测未知节点类别，更贴近实际应用
模块三：Prompt风格¶
设计五种prompt风格提供不同层级的启发式推理引导：Zero-shot、Zero-shot CoT、Few-shot、CoT、CoT-BAG（Build-a-Graph），从无引导到强引导逐步递进。
训练/推理¶
本文为纯评测研究，不涉及模型训练。以GPT-3.5-Turbo-0613为默认模型，解码温度设为0。同时在LLaMA2-7B/13B、Qwen2-7B、Mistral-7B、Vicuna-7B等开源模型上验证泛化性。
实验¶
表1：传统图任务（Table 1）¶
| 任务 | Random | BFS | DFS | PR | PPR |
|---|---|---|---|---|---|
| 连通性 | 78.36 | 89.43(↑14.1%) | 85.21(↑8.8%) | 83.79(↑6.9%) | 82.50(↑5.3%) |
| 环检测 | 64.50 | 72.71(↑12.7%) | 67.93(↑5.3%) | 69.14(↑7.2%) | 67.72(↑5.0%) |
| 哈密顿路径 | 31.50 | 42.86(↑36.1%) | 52.43(↑66.4%) | 37.64(↑19.5%) | 37.93(↑20.4%) |
| 拓扑排序 | 46.93 | 55.43(↑18.1%) | 63.21(↑34.7%) | 53.14(↑13.2%) | 54.93(↑17.1%) |
| 最短路径 | 30.14 | 51.29(↑70.2%) | 45.43(↑50.7%) | 41.21(↑36.7%) | 42.86(↑42.2%) |
表2：节点分类任务（Table 2）¶
| 数据集(Ego) | Random | BFS | DFS | PR | PPR |
|---|---|---|---|---|---|
| CORA | 70.00 | 72.00 | 71.33 | 75.33(↑7.6%) | 73.33 |
| Citeseer | 67.33 | 68.67 | 68.66 | 71.33(↑5.9%) | 69.33 |
| Pubmed | 72.00 | 74.00 | 77.33 | 82.67(↑14.8%) | 77.33 |
关键发现¶
- 有序描述全面优于随机描述：所有四种有序描述在所有任务上均超越随机baseline，BFS在最短路径任务上提升高达70.2%。
- 任务复杂度决定鲁棒性：简单任务（连通性、环检测）对描述顺序的方差低、鲁棒性强；复杂任务（哈密顿路径、最短路径）方差大、敏感性高。
- 不同任务偏好不同顺序：局部推理任务（连通性、环检测、最短路径）偏好BFS的层级遍历；全局推理任务（哈密顿路径、拓扑排序）偏好DFS的深度探索；节点分类偏好PR的全局重要性排序。
- CoT不能缓解注意力偏差：即使使用CoT引导"慢思考"，描述顺序带来的性能方差并未显著降低。
- 最短路径排序实验：设计"最短路径顺序"和"最长路径顺序"两种极端序，发现即使与答案的重叠度最高，准确率也远未达到100%，说明有序描述确实增强了LLM对图结构的理解，而非简单的答案泄露。
亮点¶
- 首次提出"图描述顺序"这一被忽视的研究视角，实验设计简洁但insight深刻
- 提出"注意力偏差"(attention bias)假说解释现象：LLM的位置编码和注意力机制在处理无序图描述时效率低下
- 任务-顺序匹配关系的分析具有很强的实践指导意义（如最短路径用BFS、哈密顿用DFS）
- 深度探索实验（极端顺序对比）有效排除了"答案泄露"的替代假说
- 构建了GraphDO数据集，包含8,500个案例，覆盖6类任务
局限¶
- 未探索不同图结构类型（稀疏/稠密、小世界、无标度等）对效果的影响
- 缺乏严格的数学/理论解释，"注意力偏差"假说停留在定性层面
- 图规模受限于LLM上下文窗口，未评估大规模图上的表现
- 未探索更先进的LLM（如GPT-4）是否仍有同样的顺序敏感性
- 仅使用ER随机图生成传统任务数据，可能无法代表真实世界图的特性
相关工作¶
- LLM推理：ReAct（Yao et al., 2022）、Self-Refine（Madaan et al., 2023）、Reflexion（Shinn et al., 2023）、LATS（Zhou et al., 2023）等推理框架
- LLM图推理：NLGraph基准（Wang et al., 2023a）提出Build-a-Graph和Algorithmic prompting；Talk like a Graph（Fatemi et al., 2023）首次系统比较图编码方法；GITA（Wei et al., 2024）引入视觉图到图推理
- Prompt工程：本文属于prompt engineering在图领域的应用，关注的是图结构的序列化表示对prompt效果的影响
评分¶
- 新颖性: ⭐⭐⭐⭐ — 首次系统研究图描述顺序，视角独特且被前人完全忽视
- 有效性: ⭐⭐⭐⭐ — 实验全面（6任务×4顺序×5prompt×6模型），结论一致可靠
- 实用性: ⭐⭐⭐⭐ — 直接指导实际图推理任务中的prompt设计策略
- 清晰度: ⭐⭐⭐⭐ — 论文结构清晰，三个研究问题逐层递进，可视化丰富