Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models
  Lifted inference algorithms commonly exploit symmetries in a probabilistic
graphical model (PGM) for efficient inference. However, existing algorithms for
Boolean-valued domains can identify only those pairs of states as symmetric, in
which the number of ones and zeros match exactly (count symmetries). Moreover,
algorithms for lifted inference in multi-valued domains also compute a
multi-valued extension of count symmetries only. These algorithms miss many
symmetries in a domain. In this paper, we present first algorithms to compute
non-count symmetries in both Boolean-valued and multi-valued domains. Our
methods can also find symmetries between multi-valued variables that have
different domain cardinalities. The key insight in the algorithms is that they
change the unit of symmetry computation from a variable to a variable-value
(VV) pair. Our experiments find that exploiting these symmetries in MCMC can
obtain substantial computational gains over existing algorithms.
