論文の概要: RIDGECUT: Learning Graph Partitioning with Rings and Wedges

• arxiv url: http://arxiv.org/abs/2505.13986v3
• Date: Mon, 11 Aug 2025 06:26:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 16:55:52.76787
• Title: RIDGECUT: Learning Graph Partitioning with Rings and Wedges
• Title（参考訳）: RIDGECUT: リングとウェッジによるグラフ分割学習
• Authors: Qize Jiang, Linsey Pang, Alice Gatti, Mahima Aggarwal, Giovanna Vantini, Xiaosong Ma, Weiwei Sun, Sourav Medya, Sanjay Chawla,
• Abstract要約: RIDGECUTは、正規化カット問題における構造認識分割を強制するために、アクション空間を制約する最初のRLフレームワークである。 本手法は,グラフを線形あるいは円形構造に置き換え,分割作業を簡略化する。
• 参考スコア（独自算出の注目度）: 15.380998112133389
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement Learning (RL) has proven to be a powerful tool for combinatorial optimization (CO) problems due to its ability to learn heuristics that can generalize across problem instances. However, integrating knowledge that will steer the RL framework for CO solutions towards domain appropriate outcomes remains a challenging task. In this paper, we propose RIDGECUT, the first RL framework that constrains the action space to enforce structure-aware partitioning in the Normalized Cut problem. Using transportation networks as a motivating example, we introduce a novel concept that leverages domain knowledge about urban road topology -- where natural partitions often take the form of concentric rings and radial wedges. Our method reshapes the graph into a linear or circular structure to simplify the partitioning task so that we can apply sequential transformers and enables efficient learning via Proximal Policy Optimization. The resulting partitions are not only aligned with expected spatial layouts but also achieve lower normalized cuts compared to existing methods. While we focus on traffic data, our approach is broadly applicable and offers a mechanism for embedding structural priors into RL for graph partitioning.
• Abstract（参考訳）: 強化学習(Reinforcement Learning, RL)は、問題インスタンスをまたいで一般化可能なヒューリスティックを学習する能力から、組合せ最適化(CO)問題のための強力なツールであることが証明されている。 しかしながら、COソリューションのRLフレームワークをドメインの適切な結果に向けて活用する知識の統合は、依然として難しい課題です。 本稿では、正規化カット問題における構造認識分割を強制するために、アクション空間を制約する最初のRLフレームワークであるRIDGECUTを提案する。 交通ネットワークをモチベーションの例として、都市の道路トポロジに関するドメイン知識を活用する新しい概念を紹介します。 提案手法は,グラフを線形あるいは円形構造に再設定することで分割作業を簡略化し,シーケンシャルトランスフォーマーを適用し,近似ポリシー最適化による効率的な学習を可能にする。 得られたパーティションは、期待される空間配置と一致しているだけでなく、既存の方法に比べて低い正規化カットを実現している。 トラフィックデータにフォーカスする一方で、我々のアプローチは広く適用可能であり、グラフ分割のために構造的事前をRLに埋め込むメカニズムを提供する。

関連論文リスト

• A Minimum Description Length Approach to Regularization in Neural Networks [2.446672595462589]
  正規化手法の選択は形式言語で訓練する上で重要な役割を担っていることを示す。 既存の正規化手法とは異なり、MDLは過剰適合を効果的に防止し、一般化を促進するために適切な帰納バイアスを導入する。
  論文  参考訳（メタデータ） (2025-05-19T17:34:56Z)
• Towards graph neural networks for provably solving convex optimization problems [5.966097889241178]
  提案するMPNNフレームワークは,検証可能な実現可能性保証を用いて凸最適化問題を解決する。 実験の結果,提案手法は既存の神経ベースラインよりも解の質や実現可能性に優れていた。
  論文  参考訳（メタデータ） (2025-02-04T16:11:41Z)
• Evolving Generalizable Parallel Algorithm Portfolios via Domain-Agnostic Instance Generation [27.138566940625385]
  一般化は、データからトレーニングする際の中核的な目的である。 並列アルゴリズムポートフォリオ(PAP)とインスタンス人口を同時に進化させることによって、共進化的アプローチはこの課題に対処する。 本研究は,パラメタライズドサーチ(DACE)のドメインに依存しない共進化という,汎用的で既成のPAP構築手法を提案する。
  論文  参考訳（メタデータ） (2025-01-06T10:29:48Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• 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)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Towards Principled Disentanglement for Domain Generalization [90.9891372499545]
  機械学習モデルの根本的な課題は、アウト・オブ・ディストリビューション(OOD)データへの一般化である。 私たちはまず、DEC(Disentanglement-Constrained Domain Generalization)と呼ばれる制約付き最適化としてOOD一般化問題を定式化する。 この変換に基づいて、結合表現の不絡合と領域一般化のための原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-27T07:36:32Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems [2.335152769484957]
  我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。 提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
  論文  参考訳（メタデータ） (2020-11-19T20:52:48Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)

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

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