論文の概要: RamseyGadgets: A Graph Construction Dataset for LLMs

• arxiv url: http://arxiv.org/abs/2608.14999v1
• Date: Sat, 15 Aug 2026 03:15:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.157318
• Title: RamseyGadgets: A Graph Construction Dataset for LLMs
• Title（参考訳）: RamseyGadgets: LLM用のグラフ構築データセット
• Abstract要約: textbfRamseyGadgetsは70の未探索グラフ構築問題のデータセットである。 これらの問題は、特別な性質を持つラムゼー良いグラフを見つける必要がある。 我々のデータセットは簡単に拡張可能であり、避けられている単色部分グラフを変更すれば、新しい問題の集合を得ることができる。
• 参考スコア（独自算出の注目度）: 1.4782129768183936
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce \textbf{RamseyGadgets}, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.
• Abstract（参考訳）: 特殊グラフの構築は、グラフ理論と計算機科学における重要な課題である。 多くの人気のあるグラフ構造は、関連するグラフと人間の創発性を包括的に探求した結果である。 数学における生成的AI利用の台頭を考えると、LSMがその推論能力を用いて特定の特性を持つグラフを構築できるかどうかを検証することは自然である。 残念なことに、ラムゼイグラフ(例えば特定の単色部分グラフを避けること)の発見のような多くの自然グラフ構築問題は、文献で広く研究されており、LLMの推論能力の産物であるのか、あるいはトレーニングデータからの再構成であるのかを確認することは困難である。 本稿では,Ramsey-good graphs with special properties (e g , containing a edge with a fixed color) を求める70の未探索グラフ構築問題からなる新しいデータセットである \textbf{RamseyGadgets} を紹介する。 これらの問題には、SATソルバによって検証可能な、合理的な大きさの解(ほとんどの10頂点)があり、自動評価に適している。 我々のデータセットは簡単に拡張可能であり、避けられている単色部分グラフを変更すれば、新しい問題の集合を得ることができる。 我々は、データセット上で5つのオープンソースLCMの性能を評価し、その結果を報告する。 その結果,LLMはデータセットのハード層問題に対して37.70%の精度しか達成せず,Gemma-4-31Bは5つの中で最高性能を達成していることがわかった。 また、当社のデータセットによって、このタスクにおいてLLMがより良く機能する上で、どのようなヒントが役立つかを確認できます。

関連論文リスト

• Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks [4.0636315905272475]
  実世界のデータでは、グラフのサイズは著しく大きくなり、多くの場合、完全にアクセスできない。 大規模グラフベンチマークデータセットであるEstGraphを提案し,大規模グラフ特性を推定するための4つの異なるタスクを提案する。 我々は,これらのタスクにおけるLLMの推論能力について,多種多様なグラフデータセットを用いて評価する。
  論文  参考訳（メタデータ） (2026-05-02T15:11:52Z)
• AGRAG: Advanced Graph-based Retrieval-Augmented Generation for LLMs [15.570965946461255]
  グラフベースの検索強化生成(RAG)は構造化知識でLarge Language Models(LLMs)を増強する大きな可能性を証明している。 既存の手法では、不正確なグラフ構築、不適切な推論能力、不適切な解答の3つの重要な課題に直面している。 本稿では,高度なグラフベースの検索拡張生成フレームワークであるAGRAGを提案する。
  論文  参考訳（メタデータ） (2025-11-02T06:13:06Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  大規模言語モデル(LLM)は、期待される推論能力と推論能力のために、AIコミュニティで再編成されている。 我々は、グラフのこのようなパラメトリック表現、グラフ法則は、LLMがグラフデータを入力として理解させるソリューションであると信じている。
  論文  参考訳（メタデータ） (2024-10-16T00:01:31Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [70.03602551880526]
  グラフを処理するために,大規模言語モデル(LLM)のベンチマークであるProGraphを導入する。 その結果,現在のLCMの性能は不満足であり,最高のモデルでは36%の精度しか達成できないことがわかった。 本研究では,6つの広く使用されているグラフライブラリに基づいて,クローリングされたドキュメントと自動生成コードを含むLLM4Graphデータセットを提案する。
  論文  参考訳（メタデータ） (2024-09-29T11:38:45Z)
• Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path [53.71787069694794]
  大規模言語モデル(LLM)のグラフ推論能力に着目する。 グラフ記述変換,グラフ接続,最短パス問題という3つの基本グラフタスクにおけるLLMの能力を再考する。 この結果から,LLMはテキスト記述によるグラフ構造理解に失敗し,これらの基本課題に対して様々な性能を示すことが可能であることが示唆された。
  論文  参考訳（メタデータ） (2024-08-18T16:26:39Z)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。 既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。 本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-04-10T15:41:53Z)
• Can Graph Descriptive Order Affect Solving Graph Problems with LLMs? [55.5662721046769]
  大規模言語モデル(LLM)は、数学的推論や論理的推論を含む推論タスクにおいて大きな成功を収めた。 従来の研究は様々な手法を用いてLSMのグラフ推論能力について研究してきた。 重要な要素は、主に見過ごされ、グラフ記述がモデルに提示される即時順序である。
  論文  参考訳（メタデータ） (2024-02-11T09:46:24Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。 自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
  論文  参考訳（メタデータ） (2023-05-17T08:29:21Z)
• Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via Prompt Augmented by ChatGPT [10.879701971582502]
  我々は,複雑なグラフデータに対する推論能力を備えた大規模言語モデル(LLM)の開発を目指している。 最新のChatGPTおよびToolformerモデルに触発された我々は、外部グラフ推論APIツールを使用するために、ChatGPTによって強化されたプロンプトでLLM自体を教えるためのGraph-ToolFormerフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-04-10T05:25:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。