摘要

GraphArena是一项针对大型语言模型（LLMs）在图计算问题上的基准测试工具。该工具通过使用百万级规模的现实世界图数据，涵盖知识图谱、社交网络和分子结构等多种场景，评估LLMs在图计算任务上的推理能力。GraphArena包含10个计算任务，包括4个多项式时间问题和6个NP完全问题，通过严格的评估框架对LLMs的输出进行分类，如正确、次优或幻觉（格式正确但不可行）。评估结果显示，即使是顶尖的LLMs在处理更大、更复杂的图问题时也会遇到困难，并存在幻觉问题。GraphArena为现有的LLM基准提供了宝贵的补充，并已开源。

原理

GraphArena的工作原理基于三个核心原则：

1. 现实图集合：使用真实世界的图数据，确保图的拓扑结构和属性的完整性。
2. 精选任务选择：提供多样化和挑战性的任务，测试LLMs的广泛推理技能，包括简单计算到复杂的多步骤分析。
3. 严格评估框架：引入任务特定的细粒度评估协议，要求LLMs识别图中的特定组件或路径以达到解决方案，并对响应进行分类，以增加评估的严格性和减少对表面模式识别的依赖。

流程

GraphArena的工作流程包括数据集收集、任务设计和评估框架三个主要部分：

1. 数据集收集：从多个来源收集真实世界的图数据，如学术数据库、社交网络和分子结构数据库。
2. 任务设计：选择适当的图计算问题子集进行基准测试，包括常见的邻居、最短距离、连通组件等任务。
3. 评估框架：开发详细的评估框架，防止基于模式的猜测，要求LLMs输出相关的图组件或路径，并通过检查器将响应分类为正确、次优、幻觉或缺失。

应用

GraphArena的应用前景广泛，特别是在需要复杂图推理的领域，如社交网络分析、知识图谱构建和分子结构研究。通过评估和改进LLMs在图计算问题上的表现，可以推动这些领域的发展，并促进LLMs向具有强大推理能力的人工通用智能迈进。