論文の概要: A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing

• arxiv url: http://arxiv.org/abs/2512.24676v1
• Date: Wed, 31 Dec 2025 07:05:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-01 23:27:28.592195
• Title: A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing
• Title（参考訳）: メッセージパッシングによるグラフ構造化非線形プログラムの新しい分解パラダイム
• Authors: Kuangyu Ding, Marie Maros, Gesualdo Scutari,
• Abstract要約: 決定変数がグラフやハイパーグラフに従って局所的に相互作用する有限サム非線形プログラムについて検討する。 本稿では,ミニサムメッセージパッシングとJacodiブロック更新を結合したグラフ対応分散フレームワークMP-Jacobiを提案する。
• 参考スコア（独自算出の注目度）: 11.765197673198983
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study finite-sum nonlinear programs whose decision variables interact locally according to a graph or hypergraph. We propose MP-Jacobi (Message Passing-Jacobi), a graph-compliant decentralized framework that couples min-sum message passing with Jacobi block updates. The (hyper)graph is partitioned into tree clusters. At each iteration, agents update in parallel by solving a cluster subproblem whose objective decomposes into (i) an intra-cluster term evaluated by a single min-sum sweep on the cluster tree (cost-to-go messages) and (ii) inter-cluster couplings handled via a Jacobi correction using neighbors' latest iterates. This design uses only single-hop communication and yields a convergent message-passing method on loopy graphs. For strongly convex objectives we establish global linear convergence and explicit rates that quantify how curvature, coupling strength, and the chosen partition affect scalability and provide guidance for clustering. To mitigate the computation and communication cost of exact message updates, we develop graph-compliant surrogates that preserve convergence while reducing per-iteration complexity. We further extend MP-Jacobi to hypergraphs; in heavily overlapping regimes, a surrogate-based hyperedge-splitting scheme restores finite-time intra-cluster message updates and maintains convergence. Experiments validate the theory and show consistent improvements over decentralized gradient baselines.
• Abstract（参考訳）: 決定変数がグラフやハイパーグラフに従って局所的に相互作用する有限サム非線形プログラムについて検討する。 本稿では,MP-Jacobi(Message Passing-Jacobi)を提案する。 ハイパーグラフはツリークラスタに分割される。 各イテレーションでエージェントは、目的が分解されるクラスタサブプロブレムを解決して、並列に更新する。 (i)クラスタツリー(コスト・ツー・ゴー・メッセージ)上の単一のminサム・スイープによって評価されたクラスタ内用語及び (II)隣人の最新のイテレーションを用いたジャコビ補正によりクラスタ間カップリングを処理した。 この設計はシングルホップ通信のみを使用し、ループグラフ上の収束メッセージパス法を生成する。 強凸目的のために、曲率、結合強度、選択された分割がスケーラビリティにどのように影響するかを定量化し、クラスタリングのためのガイダンスを提供する、大域的な線形収束と明示的な速度を確立する。 正確なメッセージ更新の計算と通信コストを軽減するため,グラフ対応サロゲートを開発した。 我々はさらにMP-Jacobiをハイパーグラフに拡張し、重重なり合うレシエーションにおいて、サロゲートベースのハイパーエッジ分割スキームは、有限時間クラスタ内メッセージ更新を復元し、収束を維持する。 実験は理論を検証し、分散勾配ベースラインよりも一貫した改善を示す。

関連論文リスト

• Quantum-Assisted Correlation Clustering [3.8448698053186843]
  この研究は、グラフベースの教師なし学習タスクである相関クラスタリングのためのハイブリッド量子古典的手法を導入する。 我々は、もともと連立構造生成のために設計された量子支援型解法GCS-Qを適用し、署名付きグラフにおけるクラスタ内合意を最大化する。 合成符号グラフと実世界のハイパースペクトル画像データに関する実証的な評価は、相関クラスタリングに適応すると、GCS-Qはロバスト性およびクラスタリング品質において古典的アルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2025-09-03T12:14:35Z)
• Deep Cut-informed Graph Embedding and Clustering [36.17182061654739]
  我々は,革新的で非GNNベースのDeep Cut-informed Graph Embedding and Clusteringフレームワーク,すなわちDCGCを提案する。 符号化モジュールに対しては,その結合正規化カットを最小化することにより,グラフ構造と属性を融合させる,カットインフォームドグラフ埋め込みの目的を導出する。 クラスタリングモジュールでは,クラスタリングの割り当てを得るために最適な輸送理論を利用する。
  論文  参考訳（メタデータ） (2025-03-09T14:24:09Z)
• Graph Transformer GANs with Graph Masked Modeling for Architectural Layout Generation [153.92387500677023]
  本稿では,グラフノード関係を効果的に学習するために,GTGAN(Graph Transformer Generative Adversarial Network)を提案する。 提案したグラフ変換器エンコーダは、局所的およびグローバルな相互作用をモデル化するために、Transformer内のグラフ畳み込みと自己アテンションを組み合わせる。 また,グラフ表現学習のための自己指導型事前学習手法を提案する。
  論文  参考訳（メタデータ） (2024-01-15T14:36:38Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Deep Temporal Graph Clustering [77.02070768950145]
  深部時間グラフクラスタリング(GC)のための汎用フレームワークを提案する。 GCは、時間グラフの相互作用シーケンスに基づくバッチ処理パターンに適合するディープクラスタリング技術を導入している。 我々のフレームワークは、既存の時間グラフ学習手法の性能を効果的に向上させることができる。
  論文  参考訳（メタデータ） (2023-05-18T06:17:50Z)
• ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
  密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。 我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
  論文  参考訳（メタデータ） (2023-01-28T11:10:50Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural Networks [24.017988997693262]
  ノードとノードのクラスタメンバーシップ間の接続が時間とともに変化する可能性がある動的グラフにおけるノードのクラスタリングの問題を検討する。 まず,ノード間の重み付き接続に基づいてノードをクラスタ化し,その重みが時間とともに一定速度で減少する,簡易な崩壊ベースのクラスタリングアルゴリズムを提案する。 本稿では,各クラスタの最適減衰率を特徴付け,真のクラスタのほぼ完全回復を実現するクラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2020-12-16T04:31:19Z)

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

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