Fugu-MT 論文翻訳(概要): One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction

論文の概要: One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction

arxiv url: http://arxiv.org/abs/2208.10227v1
Date: Mon, 22 Aug 2022 12:09:19 GMT
ステータス: 処理完了
システム内更新日: 2022-08-23 12:14:16.990432
Title: One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction
Title（参考訳）: 制約満足のための高速なグローバル検索ヒューリスティックとしてのCSP:グラフニューラルネットワークの一モデル
Authors: Jan T\"onshoff, Berke Kisin, Jakob Lindner, Martin Grohe
Abstract要約: 本稿では,制約満足度問題(CSP)のエンドツーエンド探索としてトレーニング可能な汎用グラフニューラルネットワークアーキテクチャを提案する。我々のアーキテクチャは、純粋にデータ駆動方式で任意のCSPに問題固有のものを生成するために、ポリシー勾配降下で教師なしで訓練することができる。
参考スコア（独自算出の注目度）: 1.9813182042770607
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search heuristic for any Constraint Satisfaction Problem (CSP). Our architecture can be trained unsupervised with policy gradient descent to generate problem specific heuristics for any CSP in a purely data driven manner. The approach is based on a novel graph representation for CSPs that is both generic and compact and enables us to process every possible CSP instance with one GNN, regardless of constraint arity, relations or domain size. Unlike previous RL-based methods, we operate on a global search action space and allow our GNN to modify any number of variables in every step of the stochastic search. This enables our method to properly leverage the inherent parallelism of GNNs. We perform a thorough empirical evaluation where we learn heuristics for well known and important CSPs from random data, including graph coloring, MaxCut, 3-SAT and MAX-k-SAT. Our approach outperforms prior approaches for neural combinatorial optimization by a substantial margin. It can compete with, and even improve upon, conventional search heuristics on test instances that are several orders of magnitude larger and structurally more complex than those seen during training.
Abstract（参考訳）: 本稿では,任意の制約満足度問題(CSP)に対して,エンドツーエンドの探索ヒューリスティックとしてトレーニング可能な汎用グラフニューラルネットワークアーキテクチャを提案する。我々のアーキテクチャは、純粋にデータ駆動方式で任意のCSPに対して問題固有のヒューリスティックを生成するために、ポリシー勾配降下で教師なしで訓練することができる。このアプローチは、汎用的かつコンパクトなCSP用の新しいグラフ表現に基づいており、制約アリティ、関係性、ドメインサイズに関わらず、1つのGNNで可能なすべてのCSPインスタンスを処理できる。従来のRLベースの手法とは異なり、我々はグローバルな検索行動空間で動作し、GNNが確率探索の各ステップで変数を変更できるようにします。これにより,本手法はGNNの並列性を適切に活用することができる。グラフカラー化, MaxCut, 3-SAT および MAX-k-SAT などの乱数データから、よく知られた重要な CSP に対するヒューリスティックスを学習する実験的な評価を行う。我々のアプローチは、ニューラルネットワークの最適化に先行するアプローチをかなりのマージンで上回っている。トレーニング中に見られるものよりも数桁大きく、構造的に複雑であるテストインスタンスで、従来の検索ヒューリスティックと競合し、さらに改善することができる。

関連論文リスト

Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
論文参考訳（メタデータ） (2024-11-06T09:12:31Z)
Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文参考訳（メタデータ） (2024-07-26T03:14:13Z)
A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
我々はNP-hard Maximum Cut問題に特化しているオープンソースのベンチマークスイートMaxCut-Benchを提案する。我々は、このベンチマークを用いて、いくつかの一般的な学習ベースのアプローチの結果を体系的に相関づけたり、再現したりしようとする。以上の結果から, 学習者の数人は, ナイーブな欲求アルゴリズムを上回り得ず, タブサーチを一貫して上回っているのはそのうちの1人だけであることが示唆された。
論文参考訳（メタデータ） (2024-06-14T19:44:23Z)
Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs [13.871690454501389]
本稿では,グラフ上のCO問題を解くために,複雑なフィルタバンクと局所的な注意機構を活用する新しいGNNアーキテクチャであるGCONを紹介する。 GCONはすべてのタスクで競争力があり、他の特別なGNNベースのアプローチよりも一貫して優れています。
論文参考訳（メタデータ） (2024-05-31T00:02:07Z)
MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
論文参考訳（メタデータ） (2023-02-02T18:27:20Z)
A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
論文参考訳（メタデータ） (2022-10-14T03:43:05Z)
Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文参考訳（メタデータ） (2022-05-11T17:43:54Z)
Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文参考訳（メタデータ） (2021-12-03T14:23:05Z)
IQNAS: Interpretable Integer Quadratic Programming Neural Architecture Search [40.77061519007659]
適合ネットワークを見つけるための一般的なアプローチは、制約付きニューラルネットワークサーチ(NAS)である。従来はネットワークの精度に複雑な予測器を使用していた。 IQNAS (Interpretable Quadratic Programming Neural Architecture Search) を導入する。
論文参考訳（メタデータ） (2021-10-24T09:45:00Z)
Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
サンプルサブネットワークの性能に適合するグラフ畳み込みネットワークを訓練する。この戦略により、選択された候補集合において、より高いランク相関係数が得られる。
論文参考訳（メタデータ） (2020-04-17T19:12:39Z)

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

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