論文の概要: From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

• arxiv url: http://arxiv.org/abs/2610.03709v1
• Date: Fri, 02 Oct 2026 17:57:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.557866
• Title: From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
• Title（参考訳）: MixingからTering: メッセージパッシングによる分散最適化におけるグラフ分解
• Abstract要約: 非方向グラフ上の滑らかな凸関数の和の最小化について検討する。 エージェントは2つのエンドポイントのコスト・ツー・ゴーのメッセージの総和を最小限にすることで、割り当てられたエッジ変数を更新する。 関数の正則性、ネットワークトポロジ、選択されたパーティション間の相互作用において明示的なレートで線形収束を確立する。
• 参考スコア（独自算出の注目度）: 8.925833053270507
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the minimization of sums of smooth strongly convex functions over undirected graphs, with each function held by one agent and communication restricted to neighbors in the graph. Existing decentralized methods, whether based on gossip or on routing over spanning trees, typically use the network to mix or aggregate information to enable {\it prescribed} local optimization updates. What this communication-centered viewpoint lacks is a general framework that uses graph structure to {\it jointly} design the optimization subproblems and the cooperative computation and communication through which agents solve them cooperatively. We develop such a framework from first principles, jointly designing the linear representation of agreement constraints, the blocks of the resulting dual variables (jointly optimized), and connected cluster of agents that cooperatively solve each block subproblem over the assigned subgraph. GATE (Graph-Tearing message passing) is a first instance of this framework: one variable per edge and tree blocks. At each iteration, agents update their assigned edge variables by minimizing the sum of the two endpoint cost-to-go messages and relaxing the result. The messages are updated through local minimizations following the tree recursion. To reduce per-iteration computational and communication costs, we develop GATE-S, a surrogate variant using tractable local models and lightweight message parametrizations. We establish linear convergence with a rate explicit in the interplay among function regularity, network topology, and the chosen partition, revealing the effects of graph decomposition. Numerical experiments are conducted to validate the theoretical results and evaluate the efficiency of our algorithms.
• Abstract（参考訳）: 本研究では,非直交グラフ上の滑らかな凸関数の和の最小化について検討し,各関数を1つのエージェントで保持し,グラフ内の隣人に限定した通信を行う。 既存の分散化手法では、gossipをベースとするか、木にまたがるルーティングをベースとするかにかかわらず、通常、ネットワークを使って情報を混ぜたり集約したりして、ローカル最適化の更新を可能にする。 このコミュニケーション中心の視点に欠けているのは、グラフ構造を用いて最適化サブプロブレムを設計し、エージェントがそれらを協調的に解決する協調計算と通信を行う一般的なフレームワークである。 本稿では,合意制約の線形表現,結果の2変数のブロック(共同最適化),および割り当てられたサブグラフ上の各ブロックサブプロブレムを協調的に解決するエージェントの連結クラスタを共同で設計する。 GATE(Graph-Tearing message passing)はこのフレームワークの最初の例である。 各イテレーションでは、エージェントが割り当てられたエッジ変数を更新し、2つのエンドポイントのコスト・ツー・ゴーのメッセージの総和を最小化し、結果を緩和する。 メッセージは、ツリー再帰後のローカルの最小化によって更新される。 GATE-Sは、トラクタブルローカルモデルと軽量メッセージパラメトリゼーションを用いたサロゲート変種である。 関数正則性,ネットワークトポロジ,選択された分割間の相互作用において明示的な速度で線形収束を確立し,グラフ分解の効果を明らかにする。 理論的結果を検証し,アルゴリズムの効率性を評価するための数値実験を行った。

関連論文リスト

• Inference-Time Graph Engineering for Multi-Agent LLM Workflows [51.56038180639833]
  ReActNetは、クエリとロール特化エージェントのセットを一連の有向通信グラフにコンパイルする、トレーニング不要のフレームワークである。 ReActNetは、競争的推論コストを維持しつつ、固定トポロジと学習トポロジのベースラインを一貫して改善することを示す。
  論文  参考訳（メタデータ） (2026-09-04T23:32:11Z)
• Unifying Graph Neural Networks Through a Common Layer Equation [75.88127999406392]
  7つのコンポーネントを通して被覆されたアーキテクチャを表現する共通層方程式を導入する。 中央の因子化は、伝達銀行によってエンコードされた情報と、メッセージマップによってエンコードされた動きとを分離する。 この統合を明確化し、標準層とコンポーネント割り当ての作業的削減を通じて、チェック可能にする。
  論文  参考訳（メタデータ） (2026-08-17T04:37:59Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2026-05-13T05:24:35Z)
• A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing [11.765197673198983]
  決定変数がグラフやハイパーグラフに従って局所的に相互作用する有限サム非線形プログラムについて検討する。 本稿では,ミニサムメッセージパッシングとJacodiブロック更新を結合したグラフ対応分散フレームワークMP-Jacobiを提案する。
  論文  参考訳（メタデータ） (2025-12-31T07:05:37Z)
• Covariate-assisted graph matching [1.4466802614938332]
  そこで我々は,シードと呼ばれるノードの集合の部分的アライメントが知られている2つの新しいグラフマッチング法を提案する。 本手法の有効性は,数値実験および統計学系譜と協調ネットワークのマッチングへの応用を通じて実証された。
  論文  参考訳（メタデータ） (2025-12-12T18:12:56Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment [19.502687203792547]
  教師なしグラフアライメント(英語版)は、グラフ構造とノード特徴のみを活用することにより、一対のグラフ間のノード対応を見つける。 最近の研究の1つのカテゴリは、まずノード表現を計算し、次に最も大きな埋め込みベースの類似性を持つノードとマッチングする。 他のカテゴリは、Gromov-Wasserstein学習による最適輸送(OT)に問題を還元する。 一致したノード対と一致しないノード対を2つのグラフで区別する際のモデルの識別力について検討する。 理論解析により,より強い表現力を持つCombAlignというハイブリッドアプローチを提唱した。
  論文  参考訳（メタデータ） (2024-06-19T04:57:35Z)
• Push--Pull with Device Sampling [8.344476599818826]
  複数のエージェントが協力して、基礎となる通信グラフを交換することで、ローカル関数の平均を最小化する分散最適化問題を考察する。 ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。 理論解析により,局所目的関数が強凸である場合,アルゴリズムは線形に収束することを示した。
  論文  参考訳（メタデータ） (2022-06-08T18:18:18Z)
• BayGo: Joint Bayesian Learning and Information-Aware Graph Optimization [48.30183416069897]
  BayGoは、ベイズ学習とグラフ最適化のフレームワークである。 本研究の枠組みは、完全連結および恒星トポロジーグラフと比較して、より高速な収束と精度を実現する。
  論文  参考訳（メタデータ） (2020-11-09T11:16:55Z)

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

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