Insights Regarding the Success of Damping in Improving Belief Propagation

A common approach for solving distributed constraint optimization problems (DCOPs) is to represent them with a graphical model and to solve them with a message passing algorithm. Belief propagation is a popular and well studied such incomplete inference algorithm. Min-sum (often referred to as Max-sum) is the belief propagation version that is used for solving minimization DCOPs. Belief propagation is performed on a factor graph representation of the problem, in which the graph nodes take an active role in the algorithm, i.e., they perform calculations and exchange messages with their neighbors. Unfortunately, the standard version of Min-sum fails to converge in many cases, and produces low quality solutions. Previous studies proposed methods to encourage its convergence and improve solution quality. Recently, empirical evidence indicated that the performance of Min-sum can be immensely improved by enhancing it with damping of beliefs (constraint costs) that are exchanged by the graph nodes. However, while this was empirically validated, a theoretical understanding of this phenomenon has not yet been established. In this research, we present a number of theoretical and empirical results that achieve important milestones in understanding damping's success in improving Min-sum. These include adapting theoretical tools that were suggested for analyzing Min-sum to work with Damped Min-sum (DMS) and analyzing the effect of damping on graphs with special structures. We show that when belief propagation instantly converges, damping is redundant, and thus, the main contribution of damping is in reducing the exponential growth of the inconsistent beliefs that are propagated in the first steps of the algorithm's run.