論文の概要: Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs

• arxiv url: http://arxiv.org/abs/2505.20972v1
• Date: Tue, 27 May 2025 10:04:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.566927
• Title: Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs
• Title（参考訳）: Deep k-grouping: グラフとハイパーグラフの組合せ最適化のための教師なし学習フレームワーク
• Authors: Sen Bai, Chunqi Yang, Xin Bai, Xin Zhang, Zhengang Jiang,
• Abstract要約: 既存の教師なしニューラルネットワークソルバは、$k$-groupingの問題を解決するのに苦労している。 本研究では,教師なし学習ベースのフレームワークであるDeep $k$-groupingを提案する。
• 参考スコア（独自算出の注目度）: 2.244324685724497
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Along with AI computing shining in scientific discovery, its potential in the combinatorial optimization (CO) domain has also emerged in recent years. Yet, existing unsupervised neural network solvers struggle to solve $k$-grouping problems (e.g., coloring, partitioning) on large-scale graphs and hypergraphs, due to limited computational frameworks. In this work, we propose Deep $k$-grouping, an unsupervised learning-based CO framework. Specifically, we contribute: Novel one-hot encoded polynomial unconstrained binary optimization (OH-PUBO), a formulation for modeling k-grouping problems on graphs and hypergraphs (e.g., graph/hypergraph coloring and partitioning); GPU-accelerated algorithms for large-scale k-grouping CO problems. Deep $k$-grouping employs the relaxation of large-scale OH-PUBO objectives as differentiable loss functions and trains to optimize them in an unsupervised manner. To ensure scalability, it leverages GPU-accelerated algorithms to unify the training pipeline; A Gini coefficient-based continuous relaxation annealing strategy to enforce discreteness of solutions while preventing convergence to local optima. Experimental results demonstrate that Deep $k$-grouping outperforms existing neural network solvers and classical heuristics such as SCIP and Tabu.
• Abstract（参考訳）: 科学的な発見に輝くAIコンピューティングに加えて、組合せ最適化(CO)ドメインのポテンシャルも近年出現している。 しかし、既存の教師なしニューラルネットワークソルバは、限られた計算フレームワークのため、大規模グラフやハイパーグラフ上の$k$グループ化問題(例えば、カラー化、パーティショニング)を解決するのに苦労している。 本研究では,教師なし学習ベースのCOフレームワークであるDeep $k$-groupingを提案する。 具体的には, グラフおよびハイパーグラフ上のk群問題(例えば, グラフ/ハイパーグラフのカラー化と分割)をモデル化するための定式化, 大規模k群CO問題に対するGPU加速アルゴリズムを提案する。 Deep $k$-groupingは、大規模なOH-PUBO目標の緩和を差別化可能な損失関数として採用し、教師なしの方法でそれらを最適化する。 スケーラビリティを確保するため、GPUアクセラレーションアルゴリズムを活用してトレーニングパイプラインを統一する。Gini係数ベースの継続的緩和アニーリング戦略は、ローカルオプティマへの収束を防止しつつ、ソリューションの離散性を強制する。 実験の結果,Deep $k$-groupingは既存のニューラルネットワークソルバやSCIPやTabuといった古典的ヒューリスティックよりも優れていた。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization [3.97492577026225]
  教師なし学習を伴うグラフニューラルネットワーク(GNN)は、効率的な時間複雑性で大規模最適化問題(COP)を解決することができる。 しかし、現在の主流のバックプロパゲーションベースのトレーニングアルゴリズムは、ローカルなミニマに陥りがちである。 カオスグラフバックプロパゲーション(CGBP)というカオス学習アルゴリズムを導入し,カオスだけではなく,高い効率でトレーニングを行う。
  論文  参考訳（メタデータ） (2024-12-13T05:00:57Z)
• 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)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs [35.14404918074861]
  本研究では,グラフ上での組合せ最適化問題に対する教師なし学習フレームワークを提案する。 エルドスの確率論的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメータ化する。 ネットワークが適切に選択された損失に最適化された場合、学習された分布は、制御された確率、低コストな積分解を含むことを示す。
  論文  参考訳（メタデータ） (2020-06-18T16:13:36Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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