Belief propagation is a message-passing algorithm in which each variable in a probabilistic model repeatedly tells its neighbors what it believes about their values. It is exact on tree-shaped graphs. On graphs with cycles ("loopy" belief propagation) it often oscillates or stalls, because a node's own message travels around a cycle and comes back looking like independent evidence. The most effective recent fix samples random spanning trees, which are cycle-free subgraphs that touch every node. It runs exact inference on each tree and corrects for the missing edges by reweighting each kept edge by $1/\rho_{ij}$, where $\rho_{ij}$ is the probability that the edge appears in a sampled tree. That fix needs a cubic-cost global matrix computation and a fixed graph. Meanwhile, every real deployment of decentralized inference (sensor networks, robot teams, cellular base stations) runs over links that drop in and out. The decentralized-optimization literature treats such dropouts as a nuisance to be averaged away.
This note argues that the two problems cancel. A network whose links flicker on and off is already sampling sparse subgraphs for free. Suppose each node applies a simple local rule so that the links it uses in any one round form a forest, meaning a graph with no cycles. Then each edge's long-run frequency of use is a valid set of tree-reweighting coefficients. Each endpoint can measure that frequency by counting, with no global computation. Reweighting messages by these measured frequencies should turn loopy message passing over a time-varying network into a convergent, tree-reweighted scheme. Dropouts become the cycle-breaking mechanism rather than a source of staleness.
Core Claim
We propose forest-scheduled reweighted message passing. In each communication round, every node ranks its currently live neighbors using a fresh random key. It then exchanges messages only with the live neighbor of smallest key below its own, if one exists. Because each node has at most one "parent" and keys strictly decrease along parent links, the set of edges used in a round is always a forest, whatever the link pattern. This mirrors the one-neighbor-per-round communication of the finite-time-consensus graph sequences in On graphs with finite-time consensus and their use in gradient tracking. Those sequences are deterministic and globally synchronized. Ours is random and emerges from whichever links happen to be up.
Each endpoint of edge $(i,j)$ keeps the running estimate $\hat\rho_{ij}$, the fraction of rounds in which that edge was in the forest. The estimate is a convex combination of forest indicator vectors, so it lies in the forest polytope by construction. That is exactly the condition under which tree-reweighted belief propagation (TRBP) has a convex objective. The message from node $t$ to node $s$ then takes the tree-reweighted form
$$ m_{t\to s}(x_s) \propto \sum_{x_t} \psi_{st}(x_s,x_t)^{1/\hat\rho_{st}}\,\psi_t(x_t)\,\frac{\prod_{v\in N(t)\setminus s} m_{v\to t}(x_t)^{\hat\rho_{vt}}}{m_{s\to t}(x_t)^{1-\hat\rho_{st}}}. $$
Here $\psi_{st}$ and $\psi_t$ are the pairwise and single-node potentials, and $N(t)$ is the set of $t$'s neighbors in the model. This update is sent only when edge $(s,t)$ is in the current forest. If a link stays up for several rounds, the forest is swept along multiple hops before it changes. For MAP problems, where the goal is the single most likely configuration, we run the sum-product version at a decreasing temperature. This follows the equivalence between low-temperature smoothed sum-product and max-product established in Accelerated dual decomposition for MAP inference.
An honest point about what does the work: one-hop updates do not need per-round acyclicity to be well defined. Echoes form over many rounds, across the union of different forests. The per-round forest rule exists to certify that the measured weights $\hat\rho$ are valid tree-reweighting coefficients. The reweighting is what suppresses the echo. The ablations below are designed to confirm this division of labor.
Relation to Prior Work
Two papers motivate the reweighting approach and supply its method. From Fields to Random Trees samples uniform spanning trees with Wilson's algorithm, reweights edges by inverse inclusion probability computed from effective resistance, and merges per-tree solutions centrally. It showed that this beats loopy BP and TRBP on grids, random graphs, cellular networks and a 5G cell-identity instance. We keep its central insight, that inverse-inclusion reweighting tames cycles. We replace its static graph, its cubic Laplacian pseudoinverse and its centralized merge with frequencies measured by the network itself and purely local updates. Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm also breaks cycles, but it does so once and permanently. It builds a maximum spanning tree with the GHS distributed protocol and discards the other edges. Our scheme rotates through all edges over time, so no constraint is discarded, and it never needs the stable network that GHS requires.
The decentralized-optimization papers constrain the design rather than supply it. Subgradient-push (Distributed optimization over time-varying directed graphs) and Push-DIGing (Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs) handle changing graphs only under "B-strong connectivity". That condition requires the union of graphs over every window of B rounds to be connected. We borrow it as our coverage assumption: every model edge must appear in the forest at a frequency bounded below over every window. These methods also have every agent carry the full global decision vector. Our messages stay the size of one edge's variables, which is the communication argument made in A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing. That paper's MP-Jacobi, however, fixes a tree-cluster partition offline and needs complete synchronous sweeps inside each cluster. Both requirements break when links drop. Accelerated consensus via Min-Sum Splitting shows that adding directionality to min-sum removes echoes. Its analysis is limited to static graphs and quadratic objectives, and it needs the global spectral gap, so it serves as a conceptual cousin rather than a competitor on discrete inference.
The approach also speaks to a tension the research file identifies. Denser connectivity speeds up consensus, while denser short cycles destroy belief propagation, as both the echo-chamber analysis in the Bounded Max-Sum work and the replica-symmetry-breaking picture in Marc Mezard describe. Under forest scheduling, a denser link graph only raises how often each edge is covered. It never raises the number of cycles active within a single round.
Research Program
The theoretical aim is a convergence statement for the positive-temperature case. The proposed condition is that link availability is stationary, or slowly varying, and that every model edge has forest-inclusion frequency at least $\rho_{\min}>0$ over every window of length B. Under that condition, we conjecture that forest-scheduled updates, damped if necessary, converge to the fixed point of the convex tree-reweighted objective defined by the limiting weights $\rho$. The intended proof route treats each round's forest as a randomly chosen block in a block-coordinate method on the convex dual. Coverage then plays the role that strong connectivity plays in push-sum proofs. A second result would bound how far the solution moves when $\hat\rho$ is estimated rather than known, using a two-timescale argument in which the weights settle more slowly than the messages.
We will state plainly which pieces fall short of these targets. Undamped TRBP is not guaranteed to converge even with convex weights, so damping may be required in practice. The max-product limit inherits the looseness of the linear-programming relaxation documented in Sujay Sanghavi et al. and David Sontag et al.. Directed links, where only one side can hear the other, break the symmetric exchange the rule assumes. We treat them as a stress test, with per-direction frequencies, rather than as a solved case.
The engineering aim is a simulator in which a factor graph is mapped one-to-one onto agents and each edge carries a link process. We will use three link processes, all our own constructions rather than benchmark-provided ones. The first is independent per-edge dropout with heterogeneous up-probabilities. The second is bursty two-state dropout. The third is mobility-driven, where distance determines whether a link is up.
Baselines
The naive reference point is loopy max-product or sum-product with standard damping. When a link is down, each receiver simply reuses the last message it got. This is what a practitioner would deploy tomorrow. It gets the same link traces, the same round budget, and a tuned damping factor selected on held-out instances. We expect it to be the weakest of the baselines. From Fields to Random Trees reports that loopy BP and TRBP stalled at an energy of about 372M on PCI_INSTANCE_1, even with a static graph.
The strongest existing method on solution quality is the spanning-tree method (SPT) of From Fields to Random Trees, which reached about 84k energy on PCI_INSTANCE_1. We run it as an oracle. It sees the full static model graph, computes exact effective resistances centrally and merges centrally, so it gets strictly more information and computation than our method. Matching it is not required. Beating the claim means landing within a small factor of SPT's energy on the PCI instance and on the 70×70 grids, Erdős-Rényi and cellular graphs, using only local computation and only links that are actually up. A further requirement is that our method still converges at dropout rates where SPT would have to recompute its Laplacian every round.
For distributed constraint problems, the strongest decentralized competitor is Bounded Max-Sum. On random 50-agent problems with gamma-distributed payoffs it is reported "typically within 95% of the optimum", with an approximation ratio "typically 1.23" and a runtime of about 800 ms (Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm). We give it a fair chance by rebuilding its spanning tree with GHS whenever the topology has been stable long enough for GHS to finish. Beating it means higher solution quality at matched communication. Since it discards cyclic edges permanently, it should be beatable on static graphs as well.
On the protein side-chain set, the reference figures are 16 of 30 graphs solved to optimality by DW-LP, 6 by TRW-S and 1 by MPLP (Distributed Anytime MAP Inference). DW-LP uses a central master program. We will report our count alongside these rather than claim to beat DW-LP. A decentralized method approaching the TRW-S count under dropouts would already be informative.
Three ablations isolate the key ingredient. The first runs the same forest schedule with all weights set to one, which is plain BP restricted to the forest. This tests whether the schedule alone helps. The second runs TRBP with a fixed weight vector chosen from the static model graph, ignoring link statistics. This tests whether measuring the link process matters. The third replaces $\hat\rho$ with the true inclusion probabilities, computed offline. This separates estimation error from scheme error.
Why not just…?
Why not just damp loopy BP and reuse stale messages when links drop? This is the most natural competitor and could be a real threat at low dropout rates, where the scheme reduces to ordinary loopy BP. The evidence against it is that the echo pathology does not depend on link behavior: loopy BP stalls on the PCI instance even with every link up (From Fields to Random Trees). Stale messages can only make the echo worse. The stale-message baseline across a sweep of dropout rates settles the question. If it matches us at every rate, the claim fails.
Why not just rebuild a spanning tree whenever the topology changes, as Bounded Max-Sum does? Rebuilding requires the GHS protocol to finish on a stable network. Each tree also discards the cyclic edges, which bounds quality at a ratio near 1.23 (Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm). Under bursty links we expect frequent GHS restarts that never complete. The DCOP experiment with the generous rebuild schedule described above measures exactly this.
Why not smooth the MAP dual and solve it with Push-DIGing? That would provide geometric convergence over time-varying graphs (Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs). It would also require every agent to track all dual multipliers, with step sizes set from global bounds on network size and connectivity. Smoothed dual methods are also known to be slow in early iterations (Accelerated dual decomposition for MAP inference). We will run it on the 30×30 and 70×70 grids and report energy against total bytes sent, which is where its full-vector cost should show.
Why not just recompute SPT's weights centrally as the graph changes? The cost is a Laplacian pseudoinverse scaling as $O(MN^3)$ per change, followed by central merging. That is infeasible in an ad-hoc network. SPT's static quality is our oracle target, and the comparison above makes the price of decentralization explicit.
Decisive Checks
The idea lives or dies on three measurements. First, under independent dropout, our method must reach energies on PCI_INSTANCE_1 and the synthetic grids far below the stale-message loopy BP baseline and approach the SPT oracle. Second, the all-weights-equal-one ablation must lose most of that gain, confirming that reweighting by measured frequencies, not the schedule alone, does the work. Third, the estimated-weight and true-weight runs must agree closely once the frequency estimates settle, and must degrade gracefully under the bursty and mobility link models. If the first check passes and the second does not, the contribution is a scheduling trick rather than a reweighting principle, and the note's claim would be wrong.
References
- On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking
- Accelerated dual decomposition for MAP inference
- From Fields to Random Trees
- Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm
- Distributed Optimization Over Time-Varying Directed Graphs
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing
- Accelerated consensus via Min-Sum Splitting
- Optimization and Physics: On the Satisfiability of Random Boolean Formulae
- Message Passing for Max-weight Independent Set
- Tree Block Coordinate Descent for MAP in Graphical Models
- Distributed Anytime MAP Inference