論文の概要: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs

• arxiv url: http://arxiv.org/abs/2006.10643v4
• Date: Sun, 7 Mar 2021 20:10:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 12:57:40.621936
• Title: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Title（参考訳）: erdos goes neural:グラフの組合せ最適化のための教師なし学習フレームワーク
• Authors: Nikolaos Karalias, Andreas Loukas
• Abstract要約: 本研究では,グラフ上での組合せ最適化問題に対する教師なし学習フレームワークを提案する。 エルドスの確率論的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメータ化する。 ネットワークが適切に選択された損失に最適化された場合、学習された分布は、制御された確率、低コストな積分解を含むことを示す。
• 参考スコア（独自算出の注目度）: 35.14404918074861
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.
• Abstract（参考訳）: 組合せ最適化問題は、特にラベル付きインスタンスの欠如において、ニューラルネットワークにとって非常に難しい。 本研究は, グラフ上のCO問題に対する教師なし学習フレームワークを提案する。 erdosの確率的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメトリゼーションする。 ネットワークが好適に選択された損失に最適化された場合、学習された分布は、制御された確率で、組合せ問題の制約に従う低コストな積分解を含む。 確率論的存在証明は、望ましい解をデコードするためにデランディマイズされる。 本稿では,最大傾き問題に対する有効な解と局所グラフクラスタリングを実現するために,本手法の有効性を示す。 本手法は,実データと合成ハードインスタンスの双方で競合する結果を得る。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。 本稿では,GNNを組合せ最適化問題に適用できることを示す。
  論文  参考訳（メタデータ） (2024-01-11T01:15:28Z)
• 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)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation [19.582494782591386]
  本研究は,最適化(CO)問題に対する教師なし学習フレームワークを提案する。 我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。 特に、この観察は、対象が明示的に与えられていないアプリケーションにおいて、事前にモデル化される必要がある場合に、対象モデルの設計を導くことができる。
  論文  参考訳（メタデータ） (2022-07-13T06:44:17Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。 ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
  論文  参考訳（メタデータ） (2021-07-02T16:54:35Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。 本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
  論文  参考訳（メタデータ） (2020-01-03T11:01:52Z)

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

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