  We introduce a novel approach to Maximum A Posteriori inference based on
discrete graphical models. By utilizing local Wasserstein distances for
coupling assignment measures across edges of the underlying graph, a given
discrete objective function is smoothly approximated and restricted to the
assignment manifold. A corresponding multiplicative update scheme combines in a
single process (i) geometric integration of the resulting Riemannian gradient
flow and (ii) rounding to integral solutions that represent valid labelings.
Throughout this process, local marginalization constraints known from the
established LP relaxation are satisfied, whereas the smooth geometric setting
results in rapidly converging iterations that can be carried out in parallel
for every edge.
