論文の概要: RLGT: A reinforcement learning framework for extremal graph theory

• arxiv url: http://arxiv.org/abs/2602.17276v1
• Date: Thu, 19 Feb 2026 11:25:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-20 15:21:28.994438
• Title: RLGT: A reinforcement learning framework for extremal graph theory
• Title（参考訳）: RLGT:極端グラフ理論のための強化学習フレームワーク
• Authors: Ivan Damnjanović, Uroš Milivojević, Irena Đorđević, Dragan Stevanović,
• Abstract要約: 強化学習(Reinforcement Learning、RL)は機械学習のサブフィールドであり、時間とともに最適な意思決定戦略を自律的に学習できるモデルを開発することに焦点を当てている。 本稿では,グラフ理論の強化学習(Reinforcement Learning for Graph Theory, RLGT)について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning (RL) is a subfield of machine learning that focuses on developing models that can autonomously learn optimal decision-making strategies over time. In a recent pioneering paper, Wagner demonstrated how the Deep Cross-Entropy RL method can be applied to tackle various problems from extremal graph theory by reformulating them as combinatorial optimization problems. Subsequently, many researchers became interested in refining and extending the framework introduced by Wagner, thereby creating various RL environments specialized for graph theory. Moreover, a number of problems from extremal graph theory were solved through the use of RL. In particular, several inequalities concerning the Laplacian spectral radius of graphs were refuted, new lower bounds were obtained for certain Ramsey numbers, and contributions were made to the Turán-type extremal problem in which the forbidden structures are cycles of length three and four. Here, we present Reinforcement Learning for Graph Theory (RLGT), a novel RL framework that systematizes the previous work and provides support for both undirected and directed graphs, with or without loops, and with an arbitrary number of edge colors. The framework efficiently represents graphs and aims to facilitate future RL-based research in extremal graph theory through optimized computational performance and a clean and modular design.
• Abstract（参考訳）: 強化学習(Reinforcement Learning、RL)は機械学習のサブフィールドであり、時間とともに最適な意思決定戦略を自律的に学習できるモデルを開発することに焦点を当てている。 最近の先駆的な論文で、ワグナーは、ディープ・クロス・エントロピー・RL法が、組合せ最適化問題としてそれらを再構成することで、極端グラフ理論から様々な問題に取り組むためにどのように適用できるかを実証した。 その後、多くの研究者がワグナーが導入したフレームワークの精製と拡張に興味を持ち、グラフ理論に特化した様々なRL環境を作り出した。 さらに、RLを用いて極端グラフ理論から多くの問題を解いた。 特に、グラフのラプラシアンスペクトル半径に関するいくつかの不等式が論じられ、あるラムゼー数に対して新しい下界が得られ、禁じられた構造が長さ3と4の周期であるトゥラン型極端問題に寄与した。 本稿では,グラフ理論の強化学習(Reinforcement Learning for Graph Theory, RLGT)について述べる。 このフレームワークはグラフを効率的に表現し、最適化された計算性能とクリーンでモジュラーな設計を通じて、極端グラフ理論における将来のRLベースの研究を促進することを目的としている。

関連論文リスト

• ProGraph-R1: Progress-aware Reinforcement Learning for Graph Retrieval Augmented Generation [37.11787010202267]
  ProGraph-R1は,グラフベースの検索と多段階推論のためのプログレッシブ・エージェント・フレームワークである。 ProGraph-R1は、意味的関連性とグラフ接続性について共同で検討する構造対応のハイパーグラフ検索機構を導入している。 マルチホップ質問応答ベンチマークの実験では、ProGraph-R1は既存のGraphRAG法よりも推論精度と生成品質を一貫して改善している。
  論文  参考訳（メタデータ） (2026-01-25T08:58:44Z)
• G-reasoner: Foundation Models for Unified Reasoning over Graph-structured Knowledge [88.82814893945077]
  大規模言語モデル(LLM)は複雑な推論において優れているが、静的かつ不完全なパラメトリック知識によって制限される。 最近のグラフ強化RAG (GraphRAG) は、このギャップを補足したグラフを構築し、LLMがそれらを推論できるようにする。 G-reasonerは、様々なグラフ構造化知識を推論するためにグラフと言語基盤モデルを統合した統合フレームワークである。
  論文  参考訳（メタデータ） (2025-09-29T04:38:12Z)
• 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)
• Do We Really Need Graph Convolution During Training? Light Post-Training Graph-ODE for Efficient Recommendation [34.93725892725111]
  トレーニングレコメンデータシステム(RecSys)におけるグラフ畳み込みネットワーク(GCNs)は、絶え間なく懸念されてきた。 本稿では,学習段階におけるグラフ畳み込みの必要性を批判的に考察する。 光後学習グラフ正規分方程式(LightGODE)という革新的な方法を導入する。
  論文  参考訳（メタデータ） (2024-07-26T17:59:32Z)
• Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling [30.45126420996238]
  本稿では,完全解の符号化にグラフ表現を用いる JSSP を解くための DRL 誘導型改良法を提案する。 本研究では,2つのモジュールからなるグラフニューラルネットワークに基づく表現スキームを設計し,改良プロセス中に遭遇したグラフ内の動的トポロジと異なるタイプのノードの情報を自動的に取得する。 古典的なベンチマーク実験により,本手法が学んだ改善方針は,最先端のDRL法よりも大きなマージンで優れていることが示された。
  論文  参考訳（メタデータ） (2022-11-20T10:20:13Z)
• Learning node embeddings via summary graphs: a brief theoretical analysis [55.25628709267215]
  グラフ表現学習は多くのグラフマイニングアプリケーションにおいて重要な役割を果たすが、大規模なグラフの埋め込みを学習することは依然として問題である。 最近の研究は、グラフの要約(つまり、より小さな要約グラフへの埋め込みを学習し、元のグラフのノード埋め込みを復元することでスケーラビリティを向上させる。 本稿では,導入したカーネル行列に基づく3つの特定の埋め込み学習手法について,詳細な理論的解析を行う。
  論文  参考訳（メタデータ） (2022-07-04T04:09:50Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  本稿では,学習したグラフトポロジを外部ガイダンスなしでデータ自身で最適化する,教師なしグラフ構造学習パラダイムを提案する。 具体的には、元のデータから"アンカーグラフ"として学習目標を生成し、対照的な損失を用いてアンカーグラフと学習グラフとの一致を最大化する。
  論文  参考訳（メタデータ） (2022-01-17T11:57:29Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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