論文の概要: A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2406.11897v1
- Date: Fri, 14 Jun 2024 19:44:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-20 00:55:56.848217
- Title: A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization
- Title（参考訳）: 最大カットのためのベンチマーク:組合せ最適化のための学習的ヒューリスティック評価の標準化に向けて
- Authors: Ankur Nath, Alan Kuhnle,
- Abstract要約: 我々はNP-hard Maximum Cut問題に特化しているオープンソースのベンチマークスイートMaxCut-Benchを提案する。
我々は、このベンチマークを用いて、いくつかの一般的な学習ベースのアプローチの結果を体系的に相関づけたり、再現したりしようとする。
以上の結果から, 学習者の数人は, ナイーブな欲求アルゴリズムを上回り得ず, タブサーチを一貫して上回っているのはそのうちの1人だけであることが示唆された。
- 参考スコア（独自算出の注目度）: 12.016449555335976
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, there has been much work on the design of general heuristics for graph-based, combinatorial optimization problems via the incorporation of Graph Neural Networks (GNNs) to learn distribution-specific solution structures.However, there is a lack of consistency in the evaluation of these heuristics, in terms of the baselines and instances chosen, which makes it difficult to assess the relative performance of the algorithms. In this paper, we propose an open-source benchmark suite MaxCut-Bench dedicated to the NP-hard Maximum Cut problem in both its weighted and unweighted variants, based on a careful selection of instances curated from diverse graph datasets. The suite offers a unified interface to various heuristics, both traditional and machine learning-based. Next, we use the benchmark in an attempt to systematically corroborate or reproduce the results of several, popular learning-based approaches, including S2V-DQN [31], ECO-DQN [4], among others, in terms of three dimensions: objective value, generalization, and scalability. Our empirical results show that several of the learned heuristics fail to outperform a naive greedy algorithm, and that only one of them consistently outperforms Tabu Search, a simple, general heuristic based upon local search. Furthermore, we find that the performance of ECO-DQN remains the same or is improved if the GNN is replaced by a simple linear regression on a subset of the features that are related to Tabu Search. Code, data, and pretrained models are available at: \url{https://github.com/ankurnath/MaxCut-Bench}.
- Abstract（参考訳）: 近年,グラフニューラルネットワーク(GNN)を組み込んで分布固有の解構造を学習することで,グラフに基づく組合せ最適化問題に対する一般ヒューリスティックスの設計が盛んに行われているが,基本点と選択されたインスタンスの観点からは,これらのヒューリスティックスの評価に一貫性が欠如しているため,アルゴリズムの相対的な性能を評価することは困難である。
本稿では,NP-hard Maximum Cut問題に特化したオープンソースのベンチマークスイートMaxCut-Benchを提案する。
このスイートは、伝統的および機械学習ベースのさまざまなヒューリスティックに統一されたインターフェースを提供する。
次に,S2V-DQN [31] や ECO-DQN [4] など,ポピュラーな学習ベースアプローチの成果を,客観的な価値,一般化,拡張性の3次元の観点から体系的に相関付け,再現する試みとして,このベンチマークを用いた。
実験の結果,学習したヒューリスティックのいくつかは,単純な局所探索に基づく一般ヒューリスティックであるタブサーチを一貫して上回っている。
さらに,GNN が Tabu Search に関連する特徴のサブセット上の単純な線形回帰に置き換えられた場合,ECO-DQN の性能が変わらず改善されることが判明した。
コード、データ、事前訓練されたモデルは、以下の通りである。
関連論文リスト
- Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
論文 参考訳（メタデータ） (2024-07-23T13:34:35Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - Learning to Branch in Combinatorial Optimization with Graph Pointer
Networks [17.729352126574902]
本稿では,分岐境界における変数選択ポリシーを学習するためのグラフポインターネットワークモデルを提案する。
グラフニューラルネットワークとポインタ機構を組み合わせたモデルでは,解法状態から分岐変数決定への効果的マッピングが可能である。
論文 参考訳（メタデータ） (2023-07-04T01:56:07Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳（メタデータ） (2022-11-26T00:01:01Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33: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) - Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。
UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
論文 参考訳（メタデータ） (2022-06-21T01:46:38Z) - What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。
木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文 参考訳（メタデータ） (2022-01-25T17:37:34Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Discrete-Valued Latent Preference Matrix Estimation with Graph Side
Information [12.836994708337144]
最適なサンプルの複雑さにマッチするアルゴリズムを開発する。
我々のアルゴリズムはエラーをモデル化し、予測性能の点で既存のアルゴリズムより優れている。
論文 参考訳（メタデータ） (2020-03-16T06:29:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。