GraphARC：基于图结构的抽象推理综合基准

# GraphARC: 基于图的抽象推理综合基准 来源：https://arxiv.org/html/2605.31031 \(2026\) ###### 摘要\. 关系推理是智能的核心，但现有基准通常局限于网格或文本等格式。我们引入了*GraphARC*，一个针对图结构数据上的抽象推理基准。GraphARC 泛化了抽象推理语料库 (ARC) 的少样本变换学习范式。每个任务要求从少量输入-输出对中推断出变换规则，并将其应用于新的测试图，涵盖局部、全局和层次化的图变换。与基于网格的 ARC 不同，GraphARC 实例可以在不同的图系列和规模上大规模生成，从而能够系统地评估泛化能力。我们在 GraphARC 上评估了最先进的语言模型，并观察到了明显的局限性。模型能够回答关于图属性的问题，但常常无法解决完整的图变换任务，暴露了理解与执行之间的差距。在更大的实例上，性能进一步下降，揭示了规模化障碍。更广泛地说，通过将节点分类、链接预测和图生成等任务方面整合到一个统一框架中，GraphARC 为未来的图基础模型提供了一个有前景的测试平台。 少样本、抽象推理、图、可扩展性、基准、ARC、推理模型、组合泛化 ††journalyear:2026††copyright:cc††conference:Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2; August 09–13, 2026; Jeju Island, Republic of Korea††booktitle:Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2 \(KDD ’26\), August 09–13, 2026, Jeju Island, Republic of Korea††doi:10\.1145/3770855\.3817591††isbn:979\-8\-4007\-2259\-2/2026/08††ccs:Mathematics of computing Graph theory††ccs:Computing methodologies Logical and relational learning††ccs:Computing methodologies Rule learning††ccs:Computing methodologies Natural language processing 图 1\.两个 GraphARC 任务示例，展示了图上的少样本抽象推理。每个任务呈现两个输入-输出图对（顶行和中行）来说明变换规则，随后是一个测试输入图，需要应用学到的规则。左侧示例中，变换规则将连接两个着色节点（蓝色显示）的最短路径着色。该任务限于树结构，以确保任意两个节点之间存在唯一的最短路径。右侧示例显示了一个任务，其中移除不同颜色节点之间的边。## 1\.引言 关系推理——感知和推理对象之间关系的能力——是智能的核心方面（Hummel and Holyoak,2003 (https://arxiv.org/html/2605.31031#bib.bib24) ; Halford et al\.,2010 (https://arxiv.org/html/2605.31031#bib.bib21) ）。这种能力支撑着许多高级认知形式：我们用它来理解跨领域的类比（Holyoak,2012 (https://arxiv.org/html/2605.31031#bib.bib22)），学习和理解语言（Pinker,1998 (https://arxiv.org/html/2605.31031#bib.bib25)），以及通常将抽象规则应用于新颖情境（Smith et al\.,1992 (https://arxiv.org/html/2605.31031#bib.bib23) ）。实现这种泛化是人工智能的核心挑战（Chollet,2019 (https://arxiv.org/html/2605.31031#bib.bib1) ; Lake et al\.,2017 (https://arxiv.org/html/2605.31031#bib.bib32) ）。抽象推理语料库 (ARC)（Chollet,2019 (https://arxiv.org/html/2605.31031#bib.bib1) ）是评估 AI 抽象推理的一个广泛认可的基准。ARC 由基于网格的视觉谜题组成，要求系统根据少量示例学习和应用变换规则。虽然 ARC 谜题是基于网格的，但许多底层规则是关系性的——分组相同的对象、复制子模式或将属性传播到相邻对象。为了更直接地捕捉这种结构，我们提出使用图作为一种更通用的表示形式，不依赖于特定的空间布局。受 ARC 启发，我们引入了*GraphARC*，一个用于图上的少样本抽象推理基准。每个任务包括 2-3 个输入-输出图对，展示变换规则，以及一个需要应用该规则的测试输入。参见图 1 (https://arxiv.org/html/2605.31031#S0.F1) 的示例。变换基于基本的图基元：局部结构（度、邻域、团集）、可达性（连通分支、孤立节点）或层次关系（树中最近的共同祖先）。变换可以是基于颜色的（更改某些节点的颜色）和结构修改，添加或移除节点和边。实例在不同图系列和大小的图上自动生成，提供了几乎无限的实例供应。这种设置允许测试模型是否能在不同大小和结构的图上泛化相同的变换。GraphARC 结合了传统图学习任务的元素，包括节点分类（Kipf and Welling,2017 (https://arxiv.org/html/2605.31031#bib.bib26) ）、图分类（Ying et al\.,2018 (https://arxiv.org/html/2605.31031#bib.bib27) ）、链接预测（Zhang and Chen,2018 (https://arxiv.org/html/2605.31031#bib.bib28) ）和图生成（Simonovsky and Komodakis,2018 (https://arxiv.org/html/2605.31031#bib.bib29) ）在一个统一框架内。鉴于缺乏广泛适用的图基础模型 (GFMs)（Liu et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib30) ; Wang et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib31) ），我们专注于评估能够处理图的文本表示的大型语言模型 (LLMs)。为此，我们系统地测试了一系列编码方案和提示选择。我们还设计了两种互补的 LLM 评估流程：一种衡量完整图变换任务的性能，另一种使用关于输入和输出图属性的针对性问题。这使我们能够将模型理解变换的能力与执行变换的能力分离开来。具体来说，GraphARC 提供了 1. \(1\) 一个可扩展的任务生成框架，能够在多种图系列上以任意规模产生多样的图变换挑战，2. \(2\) 一个全面的 LLM 评估方法论，以及 3. \(3\) 对当前 LLM 性能的广泛分析，揭示了结构理解上的显著差距，并识别出突出未来研究方向的关键失败模式。我们的代码可在 Github 上获取。¹¹¹https://github.com/sakupeltonen/graph-arc ## 2\.相关工作 #### 抽象推理语料库。 ARC 挑战由 Chollet \(2019 (https://arxiv.org/html/2605.31031#bib.bib1) \) 提出，建立了少样本抽象推理的范式，其中系统从最少的输入-输出示例中推断变换规则，并将其应用于新案例。尽管付出了大量努力，多年来性能一直徘徊在 33% 左右，直到最近取得突破：ARC 奖中的顶级开源参赛作品将神经推理与程序化搜索相结合，达到了大约 53% 的准确率。与此同时，OpenAI 的 o3 在 ARC-AGI-1 上达到了 75.7%（ARC Prize Foundation,2024a (https://arxiv.org/html/2605.31031#bib.bib35) ,b (https://arxiv.org/html/2605.31031#bib.bib9) ）。然而，2025 年 3 月发布的 ARC-AGI-2（Chollet et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib33) ）在很大程度上重置了该领域，前沿系统的得分约为 16%，而人类表现接近 60%，这突显了鲁棒的抽象推理仍然是一个开放问题。对我们的设置至关重要的是，领先的 ARC 求解器是针对基于网格的视觉谜题定制的，并且通常依赖于专门的流程或大量的计算资源，这使得直接应用于 GraphARC 的关系性、图结构 I/O 要么不必要，要么不切实际。因此，我们在 GraphARC 的文本图编码上评估通用 LLM，以探测抽象的图关系推理，而无需使用专门的 ARC 特定机制。 ARC 的影响导致了几个探索不同模态和任务公式的扩展。（Xu et al\.,2023 (https://arxiv.org/html/2605.31031#bib.bib3) ）专门为语言模型评估创建了 1D-ARC 任务。Assouel et al\. \(2022 (https://arxiv.org/html/2605.31031#bib.bib20) \) 开发了 Arith-MNIST，包含推理任务，其中模型必须推断应用于彩色数字的算术程序。在这个挑战中，输出是包含答案的单个数字，而不是变换后的网格。 #### 大型语言模型与图推理。 最近的工作探索了将 LLM 应用于图推理任务，结果喜忧参半。Fatemiet al\. \(2024 (https://arxiv.org/html/2605.31031#bib.bib4) \) 探索了各种文本表示及其对不同推理任务上 LLM 性能的影响。Wang et al\. \(2023 (https://arxiv.org/html/2605.31031#bib.bib5) \) 研究了当图以文本描述时，语言模型能否解决图问题，如连通性、环存在性和二分匹配。Dai et al\. \(2024 (https://arxiv.org/html/2605.31031#bib.bib13) \) 通过检测、转换和修改等任务评估 LLM 如何理解图模式，其中模式以自然语言或边列表指定。这项工作可以说是与我们的工作最相似，但它侧重于推理预定义的基序，而我们则针对少样本学习和一般图变换的应用。除了以文本形式输入图，Zhao et al\. \(2023 (https://arxiv.org/html/2605.31031#bib.bib34) \) 引入了 GIMLET，使用自定义的位置编码将语言模型与图结构数据集成，用于分子属性预测。Sanford et al\. \(2024 (https://arxiv.org/html/2605.31031#bib.bib41) \) 研究了不同模型大小的 Transformer 解决基于图的推理问题能力如何。虽然他们没有使用自然语言表示图，但确实表明 Transformer 可以解决他们训练过的图问题。关于 LLM 处理图问题的全面综述，请参见（Jin et al\.,2024 (https://arxiv.org/html/2605.31031#bib.bib10) ）。思维链提示（或测试时计算）已成为提高语言模型推理能力的有效方式（Wei et al\.,2022 (https://arxiv.org/html/2605.31031#bib.bib18) ; Snell et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib43) ; Mirtaheri et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib42) ）。我们将通过使用具有推理能力的闭源和开源模型（如 OpenAI 的 o3-mini 和 DeepSeek 的 R1）来研究这一点。 #### 图基础模型。 GFM 是一类新兴模型，旨在实现通用图推理。这些方法试图将 GNN 风格的结构归纳偏差与基础模型的广泛知识和少样本学习能力结合起来（Liu et al\.,2023 (https://arxiv.org/html/2605.31031#bib.bib6) ）。初步努力已针对特定领域，如知识图谱（Galkin et al\.,2024 (https://arxiv.org/html/2605.31031#bib.bib39) ）和分子图（Méndez-Lucio et al\.,2024 (https://arxiv.org/html/2605.31031#bib.bib40) ）。关于机遇和挑战的概述，请参见（Liu et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib30) ）。值得注意的是，谷歌研究院宣布了一个关系型 GFM，将数据库视为图并泛化到未见过的表，报告在垃圾邮件检测等任务上精度提升高达 40 倍。尽管进展迅速，但当前的 GFM 主要针对标准的监督目标（节点/图分类、链接预测）（Liu et al\.,2023 (https://arxiv.org/html/2605.31031#bib.bib6) ,2025 (https://arxiv.org/html/2605.31031#bib.bib30) ; Wang et al\.,2025 (https://arxiv.org/html/2605.31031#bib.bib31) ），并且不能直接适用于解决 ARC 风格的问题。因此，我们这里不对 GFM 进行基准测试；相反，GraphARC 作为未来声称具有抽象、少样本图变换能力的 GFM 的补充试验场。 ## 3\.GraphARC 表 1\.GraphARC 变换。任务分为基于颜色的变换和结构变换。参见图注 图 2\.面向 LLM 的 GraphARC 任务生成与评估流程。一个任务始于一个形式规则（例如，“将所有度为 3 的节点着色为蓝色”），该规则用于生成并文本编码一组输入-输出图示例。然后，流程分为两个不同的评估路径：1）完整输出路径（蓝色箭头）要求模型生成完整的变换后图，测试其推断规则并正确执行的能力。2）基于问题的路径（绿色箭头）通过询问关于输入图和推断出的输出属性的针对性问题来隔离理解，将理解与执行分离开。实线箭头表示进行分析或变换的阶段，而虚线箭头表示数据未经修改的流向。### 3\.1\.基准定义 一个 GraphARC 任务由 2-3 个输入-输出图对组成，演示变换规则。随后是一个测试输入图，需要应用学到的规则。参见图 1 (https://arxiv.org/html/2605.31031#S0.F1) 的示例任务。形式上，图表示为元组 G=\(V,E\)，其中节点具有从 0 到 |V|-1 的唯一整数标识符。节点 ID 在每个任务实例内保持一致。每个节点 v∈V 带有颜色属性，灰色为默认颜色。我们假设图是无向的。 GraphARC 包含 21 种不同的变换。一个任务是一个变换的一个实例。我们可以通过改变变换参数、图的大小和系列以及示例数量来为每个变换生成多个任务。此外，通过改变测试图的大小，我们可以评估模型将变换泛化到更大实例的能力。每个变换旨在测试图推理的特定方面，如局部结构（例如，基于度的着色）、可达性（连通分支、路径）或层次关系（例如，树中的共同祖先）。 #### 变换。 参见表 1 (https://arxiv.org/html/2605.31031#S3.T1) 的变换列表。我们将 GraphARC 变换组织为两个主要类别：基于颜色的变换和结构修改变换。基于颜色的任务根据结构属性修改节点颜色，而结构修改任务改变图的拓扑结构。一个完整的任务规范包括： - •变换规则：要执行的操作（例如，“将所有度为 3 的节点着色为蓝色”）。 - •所需属性：输入图必须满足的一组前提条件，以使变换有意义。例如，“colorDegree3”任务要求输入图至少有一个度为 3 的节点。这防止生成变换无效的平凡示例。 - •参数：变换的可配置元素，如目标颜色或度数。 - •变换前步骤：对输入图进行的初始修改，以设置推理问题。例如，“colorNeighbors”任务首先将一个随机节点着色为橙色，然后模型必须推断出将它的所有邻居着色为蓝色的规则。 #### 图生成与验证 我们从多个图族生成图，包括 Erdős-Rényi、Watts-Strogatz、树、星形、二分图和多分支图。这确保了