  The sum-product or belief propagation (BP) algorithm is a widely-used
message-passing algorithm for computing marginal distributions in graphical
models with discrete variables. At the core of the BP message updates, when
applied to a graphical model with pairwise interactions, lies a matrix-vector
product with complexity that is quadratic in the state dimension $d$, and
requires transmission of a $(d-1)$-dimensional vector of real numbers
(messages) to its neighbors. Since various applications involve very large
state dimensions, such computation and communication complexities can be
prohibitively complex. In this paper, we propose a low-complexity variant of
BP, referred to as stochastic belief propagation (SBP). As suggested by the
name, it is an adaptively randomized version of the BP message updates in which
each node passes randomly chosen information to each of its neighbors. The SBP
message updates reduce the computational complexity (per iteration) from
quadratic to linear in $d$, without assuming any particular structure of the
potentials, and also reduce the communication complexity significantly,
requiring only $\log{d}$ bits transmission per edge. Moreover, we establish a
number of theoretical guarantees for the performance of SBP, showing that it
converges almost surely to the BP fixed point for any tree-structured graph,
and for graphs with cycles satisfying a contractivity condition. In addition,
for these graphical models, we provide non-asymptotic upper bounds on the
convergence rate, showing that the $\ell_{\infty}$ norm of the error vector
decays no slower than $O(1/\sqrt{t})$ with the number of iterations $t$ on
trees and the mean square error decays as $O(1/t)$ for general graphs. These
analysis show that SBP can provably yield reductions in computational and
communication complexities for various classes of graphical models.
