用随机游走构建大规模图属性估计评测集，测试大模型在有限上下文下的推理能力。
Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
- 基于随机游走采样生成百万级节点的大图数据，解决上下文长度限制
- 提出4类图属性估计任务，在多个真实图数据集上验证模型表现
- 设计针对性提示模板，让大模型高效理解稀疏访问的超大规模图结构
随着大语言模型（LLMs）推理能力的提升，其在多领域应用的需求日益增长。图结构广泛存在于真实数据中，常用于表示和分析关系模式。尽管已有多个基准测试评估大模型对图算法的理解与执行能力，但受限于上下文长度，现有基准仅包含极小规模的图。在真实场景中，图往往规模巨大且部分不可访问。本文提出一个名为EstGraph的大规模图属性估计基准数据集，设计了四类任务以估计大规模图的性质。通过多种图数据集评估大模型在这些任务中的表现，并引入基于随机游走采样的任务特定提示构造方法，有效在上下文长度限制下向大模型传递足够信息，支持对包含数百万节点的图进行属性估计。
原文摘要 · Abstract (English)
With the rapidly improving reasoning abilities of Large Language Models (LLMs), there is also a rising demand to use them in a wide variety of domains. This brings about the need to carefully evaluate the limits of the capabilities of these models with various tests and benchmarks. Graph structures are ubiquitous in real-world data, and are often used to represent and analyze relationship patterns within data. Many benchmarks have already been proposed in the graph literature to test the reasoning ability of LLMs to follow and execute graph algorithms. However, due to the limited context length of LLMs, these benchmarks consist of very small graphs. In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible. In this paper, we examine a class of problems that arises with very large graphs having limited accessibility. We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties. We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets. In addition, we provide task-specific prompt constructions based on random walk sampling of large graphs (up to millions of nodes) that effectively convey sufficient information to LLMs within the limits of context length.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。