  This paper studies the form and complexity of inference in graphical models
using the abstraction offered by algebraic structures. In particular, we
broadly formalize inference problems in graphical models by viewing them as a
sequence of operations based on commutative semigroups. We then study the
computational complexity of inference by organizing various problems into an
"inference hierarchy". When the underlying structure of an inference problem is
a commutative semiring -- i.e. a combination of two commutative semigroups with
the distributive law -- a message passing procedure called belief propagation
can leverage this distributive law to perform polynomial-time inference for
certain problems. After establishing the NP-hardness of inference in any
commutative semiring, we investigate the relation between algebraic properties
in this setting and further show that polynomial-time inference using
distributive law does not (trivially) extend to inference problems that are
expressed using more than two commutative semigroups. We then extend the
algebraic treatment of message passing procedures to survey propagation,
providing a novel perspective using a combination of two commutative semirings.
This formulation generalizes the application of survey propagation to new
settings.
