Fugu-MT 論文翻訳(概要): Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks

論文の概要: Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks

arxiv url: http://arxiv.org/abs/2204.01366v1
Date: Mon, 4 Apr 2022 10:21:02 GMT
ステータス: 処理完了
システム内更新日: 2022-04-05 13:29:28.178324
Title: Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks
Title（参考訳）: エッジ重み付きグラフ畳み込みニューラルネットワークを用いた最小コストマルチカットの解法
Authors: Steffen Jung, Margret Keuper
Abstract要約: グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
参考スコア（独自算出の注目度）: 13.985534521589257
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The minimum cost multicut problem is the NP-hard/APX-hard combinatorial optimization problem of partitioning a real-valued edge-weighted graph such as to minimize the total cost of the partition. While graph convolutional neural networks (GNN) have proven to be promising in the context of combinatorial optimization, most of them are only tailored to or tested on positive-valued edge weights, i.e. they do not comply to the nature of the multicut problem. We therefore adapt various GNN architectures including Graph Convolutional Networks, Signed Graph Convolutional Networks and Graph Isomorphic Networks to facilitate the efficient encoding of real-valued edge costs. Moreover, we employ a reformulation of the multicut ILP constraints to a polynomial program as loss function that allows to learn feasible multicut solutions in a scalable way. Thus, we provide the first approach towards end-to-end trainable multicuts. Our findings support that GNN approaches can produce good solutions in practice while providing lower computation times and largely improved scalability compared to LP solvers and optimized heuristics, especially when considering large instances.
Abstract（参考訳）: 最小コストのマルチカット問題(minimum cost multicut problem)は、np-hard/apx-hard combinatorial optimization problem(np-hard/apx-hard combinatorial optimization problem)である。グラフ畳み込みニューラルネットワーク(gnn)は組合せ最適化の文脈で有望であることが証明されているが、そのほとんどは正の値のエッジウェイト(つまりマルチカット問題の性質に適合しない)でのみ調整またはテストされている。そこで我々は,グラフ畳み込みネットワーク,符号付きグラフ畳み込みネットワーク,グラフアイソモーフィックネットワークなど,さまざまなGNNアーキテクチャを適用し,実価値の高いエッジコストの効率的なエンコーディングを容易にする。さらに,マルチカット型LP制約を多項式プログラムに再構成することで,実現可能なマルチカットソリューションをスケーラブルに学習することができる。したがって、エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。 gnnのアプローチは,lpソルバや最適化ヒューリスティック,特に大規模インスタンスを考慮すれば,計算時間が少なく,スケーラビリティが大幅に向上すると同時に,実際に優れたソリューションが実現可能であることを裏付ける。

関連論文リスト

Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
論文参考訳（メタデータ） (2024-07-23T13:34:35Z)
Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。入力グラフのマルチスケール構造を捉えることが不可欠である。本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文参考訳（メタデータ） (2023-10-24T06:22:20Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
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)
Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
論文参考訳（メタデータ） (2023-10-01T00:12:31Z)
Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文参考訳（メタデータ） (2023-05-26T15:13:09Z)
Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文参考訳（メタデータ） (2022-11-16T18:59:54Z)
GNN at the Edge: Cost-Efficient Graph Neural Network Processing over Distributed Edge Servers [24.109721494781592]
グラフニューラルネットワーク(GNN)はまだ探索中であり、その広範な採用に対する大きな違いを示している。本稿では,多層ヘテロジニアスエッジネットワーク上での分散GNN処理のコスト最適化について検討する。提案手法は, 高速収束速度で95.8%以上のコスト削減を行い, デファクトベースラインよりも優れた性能が得られることを示す。
論文参考訳（メタデータ） (2022-10-31T13:03:16Z)
Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文参考訳（メタデータ） (2022-05-27T17:13:10Z)
Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
論文参考訳（メタデータ） (2021-07-02T16:54:35Z)
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文参考訳（メタデータ） (2020-08-12T08:52:50Z)

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

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