Block-Value Symmetries in Probabilistic Graphical Models
  One popular way for lifted inference in probabilistic graphical models is to
first merge symmetric states into a single cluster (orbit) and then use these
for downstream inference, via variations of orbital MCMC [Niepert, 2012]. These
orbits are represented compactly using permutations over variables, and
variable-value (VV) pairs, but they can miss several state symmetries in a
domain.
  We define the notion of permutations over block-value (BV) pairs, where a
block is a set of variables. BV strictly generalizes VV symmetries, and can
compute many more symmetries for increasing block sizes. To operationalize use
of BV permutations in lifted inference, we describe 1) an algorithm to compute
BV permutations given a block partition of the variables, 2) BV-MCMC, an
extension of orbital MCMC that can sample from BV orbits, and 3) a heuristic to
suggest good block partitions. Our experiments show that BV-MCMC can mix much
faster compared to vanilla MCMC and orbital MCMC.
