Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow
This work addresses the theoretical gap for practitioners using Belief Propagation in network flow problems, though it is incremental as it extends a known special case.
The paper tackles the problem of proving correctness and convergence for Belief Propagation algorithms in loopy graphical models by generalizing the Min-Sum Network Flow problem with relaxed constraints, and it demonstrates that the algorithm converges to the exact result.
Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.