論文の概要: Combinatorial Optimization with Automated Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2406.02872v2
- Date: Mon, 10 Jun 2024 02:45:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-11 23:15:47.821441
- Title: Combinatorial Optimization with Automated Graph Neural Networks
- Title（参考訳）: 自動グラフニューラルネットワークによる組合せ最適化
- Authors: Yang Liu, Peng Zhang, Yang Gao, Chuan Zhou, Zhao Li, Hongyang Chen,
- Abstract要約: NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。
AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
- 参考スコア（独自算出の注目度）: 28.19349828026972
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these methods is to represent a CO problem as a graph and then use GNNs to learn the node/graph embedding with combinatorial information. Although these methods have achieved promising results, given a specific CO problem, the design of GNN architectures still requires heavy manual work with domain knowledge. Existing automated GNNs are mostly focused on traditional graph learning problems, which is inapplicable to solving NP-hard CO problems. To this end, we present a new class of \textbf{AUTO}mated \textbf{G}NNs for solving \textbf{NP}-hard problems, namely \textbf{AutoGNP}. We represent CO problems by GNNs and focus on two specific problems, i.e., mixed integer linear programming and quadratic unconstrained binary optimization. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard combinatorial optimization problem. Compared with existing graph neural architecture search algorithms, AutoGNP utilizes two-hop operators in the architecture search space. Moreover, AutoGNP utilizes simulated annealing and a strict early stopping policy to avoid local optimal solutions. Empirical results on benchmark combinatorial problems demonstrate the superiority of our proposed model.
- Abstract（参考訳）: 近年、グラフニューラルネットワーク(GNN)は、最大カットや最大独立セットといったNP-hard combinatorial optimization(CO)問題を解決するために人気が高まっている。
これらの手法の背後にある中核的な考え方は、CO問題をグラフとして表現し、GNNを使用して、組み合わせ情報によるノード/グラフの埋め込みを学ぶことである。
これらの手法は、特定のCO問題を考えると、有望な結果を得たが、GNNアーキテクチャの設計にはドメイン知識による重い手作業が必要である。
既存の自動GNNは、NPハードCO問題の解決には適用できない従来のグラフ学習問題に主に焦点をあてている。
この目的のために、我々は、新しいクラスである \textbf{AUTO}mated \textbf{G}NNs を、 \textbf{NP}-ハード問題、すなわち \textbf{AutoGNP} を解決する。
我々は、GNNによるCO問題を表現するとともに、2つの特定の問題、すなわち混合整数線形計画法と2次非制約バイナリ最適化に焦点をあてる。
AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード組合せ最適化問題に対して最適なGNNを自動的に見つけることである。
既存のグラフニューラルネットワーク検索アルゴリズムと比較して、AutoGNPはアーキテクチャ検索空間の2ホップ演算子を利用する。
さらに、AutoGNPはシミュレーションアニールと厳密な早期停止ポリシーを利用して局所最適解を回避する。
ベンチマーク組合せ問題に対する実験結果から,提案モデルの有効性が示された。
関連論文リスト
- 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) - Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs [13.871690454501389]
本稿では,グラフ上のCO問題を解くために,複雑なフィルタバンクと局所的な注意機構を活用する新しいGNNアーキテクチャであるGCONを紹介する。
GCONはすべてのタスクで競争力があり、他の特別なGNNベースのアプローチよりも一貫して優れています。
論文 参考訳（メタデータ） (2024-05-31T00:02:07Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。
本稿では,GNNを組合せ最適化問題に適用できることを示す。
論文 参考訳（メタデータ） (2024-01-11T01:15:28Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳（メタデータ） (2022-11-26T00:01:01Z) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳（メタデータ） (2022-05-31T10:38:04Z) - GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed
Graph Neural Networks [68.61934077627085]
本稿では,グラフ埋め込みを学習可能なGNNと互換性のあるモデリングフレームワークであるGNNRankを紹介する。
既存の手法と比較して,我々の手法が競争力があり,しばしば優れた性能を発揮することを示す。
論文 参考訳（メタデータ） (2022-02-01T04:19:50Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳（メタデータ） (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。