Exploiting Uniform Assignments in First-Order MPE
  The MPE (Most Probable Explanation) query plays an important role in
probabilistic inference. MPE solution algorithms for probabilistic relational
models essentially adapt existing belief assessment method, replacing summation
with maximization. But the rich structure and symmetries captured by relational
models together with the properties of the maximization operator offer an
opportunity for additional simplification with potentially significant
computational ramifications. Specifically, these models often have groups of
variables that define symmetric distributions over some population of formulas.
The maximizing choice for different elements of this group is the same. If we
can realize this ahead of time, we can significantly reduce the size of the
model by eliminating a potentially significant portion of random variables.
This paper defines the notion of uniformly assigned and partially uniformly
assigned sets of variables, shows how one can recognize these sets efficiently,
and how the model can be greatly simplified once we recognize them, with little
computational effort. We demonstrate the effectiveness of these ideas
empirically on a number of models.
