論文の概要: Graph-R1: Unleashing LLM Reasoning with NP-Hard Graph Problems

• arxiv url: http://arxiv.org/abs/2508.20373v1
• Date: Thu, 28 Aug 2025 02:40:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-29 18:12:01.912108
• Title: Graph-R1: Unleashing LLM Reasoning with NP-Hard Graph Problems
• Title（参考訳）: Graph-R1:NP-Hardグラフ問題によるLLM推論の解放
• Authors: Yuyao Wang, Bowen Liu, Jianheng Tang, Nuo Chen, Yuhan Li, Qifan Zhang, Jia Li,
• Abstract要約: NP-hard(NPH)グラフ問題を新しい合成学習コーパスとして導入する。 われわれは,Long CoT Supervised Fine-Tuning and Reinforcement Learningという2段階のポストトレーニングフレームワークを開発した。 我々のフラッグシップモデルであるGraph-R1-7Bは、数学、コーディング、STEM、論理学にまたがる強力な一般化を実証します。
• 参考スコア（独自算出の注目度）: 21.63534202904903
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reasoning Large Language Models (RLLMs) have recently achieved remarkable progress on complex reasoning tasks, largely enabled by their long chain-of-thought (Long CoT) capabilities. However, developing these Long CoT behaviors relies heavily on post-training with high-quality datasets, which are typically costly and human-curated (e.g., mathematics and code), leaving scalable alternatives unexplored. In this work, we introduce NP-hard (NPH) graph problems as a novel synthetic training corpus, as they inherently require deep reasoning, extensive exploration, and reflective strategies, which are core characteristics of Long CoT reasoning. Building on this insight, we develop a two-stage post-training framework: (i) Long CoT Supervised Fine-Tuning (SFT) on rejection-sampled NPH graph instances, which substantially enhances reasoning depth, and (ii) Reinforcement Learning (RL) with a fine-grained reward design, which sharpens reasoning efficiency. Our flagship model, Graph-R1-7B, demonstrates strong generalization across mathematics, coding, STEM, and logic, and surpasses QwQ-32B on NPH graph problems in both accuracy and reasoning efficiency. These results position NPH graph problems as an effective and scalable resource for advancing Long CoT reasoning in LLMs, opening a new frontier for LLM post-training. Our implementation is available at https://github.com/Graph-Reasoner/Graph-R1, with models and datasets hosted in our Hugging Face collection HKUST-DSAIL/Graph-R1.
• Abstract（参考訳）: RLLM(Reasoning Large Language Models)は最近、複雑な推論タスクにおいて顕著な進歩を遂げました。 しかしながら、これらのLong CoTの振る舞いの開発は、高品質なデータセットによるポストトレーニングに大きく依存している。 本研究では, NP-hard(NPH)グラフ問題を合成学習コーパスとして導入する。 この洞察に基づいて、私たちは2段階のポストトレーニングフレームワークを開発します。 (i)Long CoT Supervised Fine-Tuning (SFT) on rejection-sampled NPH graph instance, which is significantly enhances reasoning depth, and。 (II)微粒な報酬設計による強化学習(RL)により推論効率が向上する。 我々のフラッグシップモデルであるGraph-R1-7Bは、数学、コーディング、STEM、論理学にまたがる強力な一般化を示し、精度と推論効率の両面でNPHグラフ上のQwQ-32Bを超える。 これらの結果から、NPHグラフ問題はLong CoT推論をLLMで進めるための有効かつスケーラブルな資源として位置づけられ、LLMポストトレーニングのための新たなフロンティアが開かれた。 私たちの実装はhttps://github.com/Graph-Reasoner/Graph-R1で公開されています。

関連論文リスト

• Graph-R1: Incentivizing the Zero-Shot Graph Learning Capability in LLMs via Explicit Reasoning [7.1931434571877375]
  グラフニューラルネットワーク(GNN)は固定ラベル空間によって制限されるが、Large Language Models(LLM)は構造的帰納バイアスを欠いている。 近年のLarge Reasoning Models (LRMs) の進歩は、明示的な長い連鎖推論を通じてゼロショットの代替手段を提供する。 本稿では,LRMによるテキスト推論問題として,ノード分類,リンク予測,グラフ分類などのグラフタスクを再構成するGNNフリーアプローチを提案する。
  論文  参考訳（メタデータ） (2025-08-24T14:49:02Z)
• Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering [75.12322966980003]
  大規模言語モデル(LLM)は、様々な領域にわたって強い帰納的推論能力を示している。 既存のRAGパイプラインのほとんどは非構造化テキストに依存しており、解釈可能性と構造化推論を制限する。 近年,知識グラフ解答のための知識グラフとLLMの統合について検討している。 KGQAにおける効率的なグラフ検索のための新しいフレームワークであるRAPLを提案する。
  論文  参考訳（メタデータ） (2025-06-11T12:03:52Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  合成グラフ理論タスクにおける強化学習(RL)はグラフ推論能力を著しく拡張することができる。 RL on ErdosでG1はグラフ推論の大幅な改善を実現し、微調整された3BモデルはQwen2.5-72B-Instruct(24倍)よりも優れています。 我々の研究は、グラフ理論上のRLでLLMを微調整することで、強力なグラフ推論器を構築するための効率的でスケーラブルな経路を提供する。
  論文  参考訳（メタデータ） (2025-05-24T04:33:41Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  グラフネットワーク(GNN)は、グラフ構造化データから学習する際、顕著な能力を示した。 最適化と一般化の観点から、GNNと一般化を比較した分析の欠如がまだ残っている。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)

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

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