  We consider inference (filtering) problems over probabilistic graphical
models with aggregate data generated by a large population of individuals. We
propose a new efficient belief propagation type algorithm over tree-structured
graphs with polynomial computational complexity as well as a global convergence
guarantee. This is in contrast to previous methods that either exhibit
prohibitive complexity as the population grows or do not guarantee convergence.
Our method is based on optimal transport, or more specifically, multi-marginal
optimal transport theory. In particular, we consider an inference problem with
aggregate observations, that can be seen as a structured multi-marginal optimal
transport problem where the cost function decomposes according to the
underlying graph. Consequently, the celebrated Sinkhorn/iterative scaling
algorithm for multi-marginal optimal transport can be leveraged together with
the standard belief propagation algorithm to establish an efficient inference
scheme which we call Sinkhorn belief propagation (SBP). We further specialize
the SBP algorithm to cases associated with hidden Markov models due to their
significance in control and estimation. We demonstrate the performance of our
algorithm on applications such as inferring population flow from aggregate
observations. We also show that in the special case where the observations are
generated by a single individual, our algorithm naturally reduces to the
standard belief propagation algorithm.
