論文の概要: Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update
- arxiv url: http://arxiv.org/abs/2407.16468v1
- Date: Tue, 23 Jul 2024 13:34:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 17:06:21.176752
- Title: Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update
- Title（参考訳）: 繰り返し機能更新による組合せ最適化におけるGNNの性能向上
- Authors: Daria Pugacheva, Andrei Ermakov, Igor Lyskov, Ilya Makarov, Yuriy Zotov,
- Abstract要約: 本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
- 参考スコア（独自算出の注目度）: 0.09986418756990156
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Combinatorial optimization (CO) problems are crucial in various scientific and industrial applications. Recently, researchers have proposed using unsupervised Graph Neural Networks (GNNs) to address NP-hard combinatorial optimization problems, which can be reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. GNNs have demonstrated high performance with nearly linear scalability and significantly outperformed classic heuristic-based algorithms in terms of computational efficiency on large-scale problems. However, when utilizing standard node features, GNNs tend to get trapped to suboptimal local minima of the energy landscape, resulting in low quality solutions. We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve CO problems with QUBO formulation. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. The proposed key components of the architecture include the recurrent use of intermediate GNN predictions, parallel convolutional layers and combination of static node features as input. Altogether, it helps to adapt the intermediate solution candidate to minimize QUBO-based loss function, taking into account not only static graph features, but also intermediate predictions treated as dynamic, i.e. iteratively changing recurrent features. The performance of the proposed algorithm has been evaluated on the canonical benchmark datasets for maximum cut, graph coloring and maximum independent set problems. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventional heuristics, improving their scalability on large instances.
- Abstract（参考訳）: 組合せ最適化(CO)問題は、様々な科学的、産業的応用において重要である。
近年,非教師付きグラフニューラルネットワーク(GNN)を用いてNP-hard組合せ最適化問題に対処する手法が提案されている。
GNNは、線形スケーラビリティに近い性能を示し、大規模問題に対する計算効率の点で、古典的ヒューリスティックなアルゴリズムを著しく上回っている。
しかしながら、標準ノード機能を利用する場合、GNNはエネルギーランドスケープの最適部分の最小値に閉じ込められ、結果として低品質の解が得られる傾向にある。
QRF-GNNと呼ばれる新しいアルゴリズムを導入し、QUBOの定式化によるCO問題を効率的に解くために、GNNのパワーを活用している。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
提案するアーキテクチャのキーコンポーネントには、中間GNN予測の繰り返し使用、並列畳み込み層、および入力として静的ノード機能の組み合わせが含まれる。
また、QUBOに基づく損失関数を最小化するために中間解候補を適応させ、静的グラフの特徴だけでなく、動的、すなわち反復的に変化する特徴として扱われる中間予測も考慮する。
提案アルゴリズムの性能は、最大カット、グラフカラー化、最大独立セット問題に対する標準ベンチマークデータセットで評価されている。
実験の結果、QRF-GNNは既存の学習ベースのアプローチを大幅に上回り、最先端の従来のヒューリスティックに匹敵し、大規模インスタンスでのスケーラビリティが向上した。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。
PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
論文 参考訳（メタデータ） (2023-11-27T19:33:14Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.566437882635872]
ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
汎用的なスケーラブルなフレームワークであるPI-GNNは、単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づいて、グラフ上の組合せ最適化(CO)問題に対処するために提案されている。
実験では,PI-GNN法と比較して最大44%改善した。
論文 参考訳（メタデータ） (2023-08-27T00:57:01Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳（メタデータ） (2022-11-26T00:01:01Z) - Inability of a graph neural network heuristic to outperform greedy
algorithms in solving combinatorial optimization problems like Max-Cut [0.0]
Nature Machine Intelligence 4, 367 (2022) において、Schuetzらは、様々な古典的なNPハード最適化問題を解決するためにニューラルネットワーク(GNN)を使用するスキームを提供している。
ネットワークがサンプルインスタンス上でどのようにトレーニングされているかを説明し、その結果のGNNは、広く使われているテクニックを適用して、その成功の可能性を判断する。
しかし, より綿密な検査により, このGNNの報告結果は勾配降下率よりもわずかに優れており, グリーディアルゴリズムにより性能が向上していることがわかった。
論文 参考訳（メタデータ） (2022-10-02T20:50:33Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-07-18T14:23:31Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - CDiNN -Convex Difference Neural Networks [0.8122270502556374]
reluアクティベーション関数を持つニューラルネットワークは、普遍関数近似が非スムース関数として関数マッピングを学ぶことが示されている。
ICNNと呼ばれる新しいニューラルネットワークアーキテクチャは、凸入力として出力を学習する。
論文 参考訳（メタデータ） (2021-03-31T17:31:16Z) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳（メタデータ） (2020-06-15T17:06:17Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳（メタデータ） (2020-02-04T20:00:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。