論文の概要: COMBHelper: A Neural Approach to Reduce Search Space for Graph
Combinatorial Problems
- arxiv url: http://arxiv.org/abs/2312.09086v2
- Date: Mon, 1 Jan 2024 15:21:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 00:51:21.046992
- Title: COMBHelper: A Neural Approach to Reduce Search Space for Graph
Combinatorial Problems
- Title(参考訳): COMBHelper: グラフコンビネーション問題に対する検索スペース削減のためのニューラルネットワーク
- Authors: Hao Tian, Sourav Medya, Wei Ye
- Abstract要約: COMBHelperは、ソリューションセットの有望なノードを特定するために、グラフニューラルネットワーク(GNN)を使用している。
また、知識蒸留(KD)モジュールと問題固有のブースティングモジュールを使用して、さらなる効率性と有効性をもたらす。
実験の結果,COMBHelperを用いた従来のCOアルゴリズムは,従来のバージョンに比べて少なくとも2倍高速であることがわかった。
- 参考スコア(独自算出の注目度): 19.442683583536137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial Optimization (CO) problems over graphs appear routinely in many
applications such as in optimizing traffic, viral marketing in social networks,
and matching for job allocation. Due to their combinatorial nature, these
problems are often NP-hard. Existing approximation algorithms and heuristics
rely on the search space to find the solutions and become time-consuming when
this space is large. In this paper, we design a neural method called COMBHelper
to reduce this space and thus improve the efficiency of the traditional CO
algorithms based on node selection. Specifically, it employs a Graph Neural
Network (GNN) to identify promising nodes for the solution set. This pruned
search space is then fed to the traditional CO algorithms. COMBHelper also uses
a Knowledge Distillation (KD) module and a problem-specific boosting module to
bring further efficiency and efficacy. Our extensive experiments show that the
traditional CO algorithms with COMBHelper are at least 2 times faster than
their original versions.
- Abstract(参考訳): グラフに対する組合せ最適化(CO)問題は、トラフィックの最適化、ソーシャルネットワークにおけるバイラルマーケティング、ジョブ割り当てのマッチングなど、多くのアプリケーションで日常的に発生する。
組み合わせの性質のため、これらの問題はしばしばNPハードである。
既存の近似アルゴリズムとヒューリスティックスは探索空間に頼って解を見つけ出し、この空間が大きくなると時間がかかる。
本論文では,この空間を削減し,ノード選択に基づく従来のCOアルゴリズムの効率を向上させるために,COMBHelperと呼ばれるニューラル手法を設計する。
具体的には、グラフニューラルネットワーク(GNN)を使用して、ソリューションセットの有望なノードを特定する。
この刈り取られた探索空間は、従来のcoアルゴリズムに供給される。
COMBHelperはまた、知識蒸留(KD)モジュールと問題固有のブースティングモジュールを使用して、さらなる効率性と有効性をもたらす。
実験の結果,COMBHelperを用いた従来のCOアルゴリズムは,従来のバージョンに比べて少なくとも2倍高速であることがわかった。
関連論文リスト
- BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳(メタデータ) (2023-12-26T03:09:08Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳(メタデータ) (2023-05-18T13:59:02Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳(メタデータ) (2022-10-31T09:46:26Z) - 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) - Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems [61.48763653120301]
クリティカルノード問題(Critical Node Problem, CNP)は、ネットワークから重要なノードの集合を見つけることを目的とした問題である。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳(メタデータ) (2021-12-03T14:23:05Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳(メタデータ) (2021-06-09T09:18:18Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳(メタデータ) (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。