From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
Abstract
We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this paradigm. We introduce a {\it graph decomposition framework} that uses the network to design the method, not merely execute it. It jointly determines how agreement is imposed, which variables are optimized jointly (blocks), and which connected subgraphs host the agents solving each block. The convergence analysis quantifies the trade-offs among these choices. GATE (Graph-Tearing message passing) instantiates the framework by assigning one dual variable per edge and partitioning the edges into trees. Agents interleave edge updates with local message passing recursions that summarize optimization within each tree (block). Its surrogate variant, GATE-S, uses tractable local models and compact messages to reduce computation and communication. We establish linear convergence and show that the topology-aware design acts as a \emph{preconditioner}: the rate depends {\it jointly} on topology and function geometry through the coupling between subproblems defined on the selected subgraphs, whereas consensus-based optimization methods pay the worst case of each separately, the centralized condition number times the inverse spectral gap. On tree-dominant graphs, convergence is provably faster: the rate scales with the tree {\it diameter}, linearly in the number of agents on rings and barbells against quadratically for non-accelerated consensus-optimization methods. Experiments support the predicted scaling and savings in iterations and communication.
Related
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- Geometry-Aware Simplicial Message Passing
- Message-passing graph persistence
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
- Efficient Message Passing for Partial Differential Equation Priors
BibTeX
@misc{ding2026from,
title = {{From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing}},
author = {Kuangyu Ding and Gesualdo Scutari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03709},
eprint = {2610.03709},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03709},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
AU - Kuangyu Ding
AU - Gesualdo Scutari
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.03709
UR - https://arxiv.org/abs/2610.03709
AB - We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this paradigm. We introduce a {\it graph decomposition framework} that uses the network to design the method, not merely execute it. It jointly determines how agreement is imposed, which variables are optimized jointly (blocks), and which connected subgraphs host the agents solving each block. The convergence analysis quantifies the trade-offs among these choices. GATE (Graph-Tearing message passing) instantiates the framework by assigning one dual variable per edge and partitioning the edges into trees. Agents interleave edge updates with local message passing recursions that summarize optimization within each tree (block). Its surrogate variant, GATE-S, uses tractable local models and compact messages to reduce computation and communication. We establish linear convergence and show that the topology-aware design acts as a \emph{preconditioner}: the rate depends {\it jointly} on topology and function geometry through the coupling between subproblems defined on the selected subgraphs, whereas consensus-based optimization methods pay the worst case of each separately, the centralized condition number times the inverse spectral gap. On tree-dominant graphs, convergence is provably faster: the rate scales with the tree {\it diameter}, linearly in the number of agents on rings and barbells against quadratically for non-accelerated consensus-optimization methods. Experiments support the predicted scaling and savings in iterations and communication.
ER -