論文の概要: A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2406.12667v1
- Date: Tue, 18 Jun 2024 14:40:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 18:28:51.207283
- Title: A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning
- Title（参考訳）: Wagnerフレームワークの体系化:グラフ理論の導出と強化学習
- Authors: Flora Angileri, Giulia Lombardi, Andrea Fois, Renato Faraone, Carlo Metta, Michele Salvi, Luigi Amedeo Bianchi, Marco Fantozzi, Silvia Giulia Galfrè, Daniele Pavesi, Maurizio Parton, Francesco Morandin,
- Abstract要約: アダム・ゾルト・ワグナー(Adam Zsolt Wagner)はReinforcement Learning (RL) を用いたグラフ理論の予想を解き放つアプローチを提案した。
様々なRLアルゴリズムを用いた4つの異なるシングルプレイヤーグラフ構築ゲームを提案する。
また、任意の予想に対して最も適切なニューラルネットワークアーキテクチャを選択するための原則的アプローチを提案する。
- 参考スコア（独自算出の注目度）: 0.3111424566471946
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In 2021, Adam Zsolt Wagner proposed an approach to disprove conjectures in graph theory using Reinforcement Learning (RL). Wagner's idea can be framed as follows: consider a conjecture, such as a certain quantity f(G) < 0 for every graph G; one can then play a single-player graph-building game, where at each turn the player decides whether to add an edge or not. The game ends when all edges have been considered, resulting in a certain graph G_T, and f(G_T) is the final score of the game; RL is then used to maximize this score. This brilliant idea is as simple as innovative, and it lends itself to systematic generalization. Several different single-player graph-building games can be employed, along with various RL algorithms. Moreover, RL maximizes the cumulative reward, allowing for step-by-step rewards instead of a single final score, provided the final cumulative reward represents the quantity of interest f(G_T). In this paper, we discuss these and various other choices that can be significant in Wagner's framework. As a contribution to this systematization, we present four distinct single-player graph-building games. Each game employs both a step-by-step reward system and a single final score. We also propose a principled approach to select the most suitable neural network architecture for any given conjecture, and introduce a new dataset of graphs labeled with their Laplacian spectra. Furthermore, we provide a counterexample for a conjecture regarding the sum of the matching number and the spectral radius, which is simpler than the example provided in Wagner's original paper. The games have been implemented as environments in the Gymnasium framework, and along with the dataset, are available as open-source supplementary materials.
- Abstract（参考訳）: 2021年、アダム・ゾルト・ワグナー (Adam Zsolt Wagner) はReinforcement Learning (RL) を用いてグラフ理論の予想を解き放つアプローチを提案した。
ワグナーの考えは、すべてのグラフ G に対してある量 f(G) < 0 のような予想を考えると、単一のプレイヤーグラフ構築ゲーム(英語版)をプレイでき、各ターンでプレイヤーがエッジを追加するかどうかを決定することができる。
ゲームは、すべてのエッジが考慮されたときに終了し、あるグラフ G_T となり、f(G_T) がゲームの最終スコアとなり、RL がこのスコアを最大化する。
この素晴らしいアイデアは革新的で、体系的な一般化に役立ちます。
様々なRLアルゴリズムとともに、いくつかの異なるシングルプレイヤーグラフ構築ゲームが利用可能である。
さらに、RLは累積報酬を最大化し、最終的な累積報酬が利息f(G_T)の量を表すならば、単一の最終スコアではなくステップバイステップの報酬を可能にする。
本稿では,ワグナーの枠組みにおいて重要な,これらおよび他の様々な選択肢について論じる。
この体系化への貢献として、我々は4つの異なるシングルプレイヤーグラフ構築ゲームを示す。
各ゲームはステップバイステップの報酬システムと1つのファイナルスコアの両方を使用する。
また、任意の予想に対して最も適切なニューラルネットワークアーキテクチャを選択するための原則的アプローチを提案し、ラプラシアンスペクトルをラベル付けしたグラフの新しいデータセットを導入する。
さらに、一致した数とスペクトル半径の和に関する予想に対する反例を示し、これはワグナーの原論文の例よりも単純である。
ゲームは、Gymnasiumフレームワークの環境として実装され、データセットとともに、オープンソースサプリメント素材として利用可能である。
関連論文リスト
- The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。
観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。
さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
論文 参考訳（メタデータ） (2024-06-18T12:16:00Z) - G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
現実のテキストグラフを対象とするフレキシブルな問合せフレームワークを開発した。
一般のテキストグラフに対する最初の検索拡張生成(RAG)手法を提案する。
G-Retrieverは、このタスクをSteiner Tree最適化問題として定式化し、グラフ上でRAGを実行する。
論文 参考訳（メタデータ） (2024-02-12T13:13:04Z) - GSINA: Improving Subgraph Extraction for Graph Invariant Learning via
Graph Sinkhorn Attention [52.67633391931959]
グラフ不変学習(GIL)は,グラフデータとそのラベル間の不変性を発見するための効果的な手法である。
グラフシンクホーン注意機構(GSINA)を提案する。
GSINAは、制御可能な空間性と柔らかさを持つ有意義で微分可能な不変部分グラフを得ることができる。
論文 参考訳（メタデータ） (2024-02-11T12:57:16Z) - MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。
最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。
本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
論文 参考訳（メタデータ） (2024-01-10T07:58:44Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。
提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文 参考訳（メタデータ） (2022-09-20T02:31:42Z) - Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
本稿では,2色グラフの入射系を基礎とするグラフ入射ゲームの解群について検討する。
アルキポフの定理は、連結グラフのグラフ入射ゲームが完全量子戦略を持つことは、それが完全古典的戦略を持つか、あるいはグラフが非平面的であることを言う。
我々はアルキポフの定理を拡張し、連結な2色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。
論文 参考訳（メタデータ） (2022-05-10T03:21:38Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games:
Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [99.00383370823839]
様々な種類の最適相関平衡を求める問題について検討する。
本稿では,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。
また、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという2つの新しいベンチマークゲームも導入した。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z) - Partial Gromov-Wasserstein Learning for Partial Graph Matching [28.47269200800775]
部分的なGromov-Wasserstein学習フレームワークは2つのグラフを部分的にマッチングするために提案される。
私たちのフレームワークはF1スコアを少なくとも20%以上改善できます。
論文 参考訳（メタデータ） (2020-12-02T14:56:22Z) - Unsupervised Graph Representation by Periphery and Hierarchical
Information Maximization [18.7475578342125]
グラフニューラルネットワークの発明により、ベクトル空間におけるノードとグラフ全体の表現の最先端性が向上した。
グラフ表現全体について、既存のグラフニューラルネットワークの大部分は、教師付き方法でグラフ分類損失に基づいてトレーニングされている。
本稿では,グラフ全体のベクトル表現を生成するための教師なしグラフニューラルネットワークを提案する。
論文 参考訳（メタデータ） (2020-06-08T15:50:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。