Abstract
Lifted inference scales to large probability models by exploiting symmetry.However, existing exact lifted inference techniques do not apply to generalfactor graphs, as they require a relational representation. In this work weprovide a theoretical framework and algorithm for performing exact liftedinference on symmetric factor graphs by computing colored graph automorphisms,as is often done for approximate lifted inference. Our key insight is torepresent variable assignments directly in the colored factor graph encoding.This allows us to generate representatives and compute the size of each orbitof the symmetric distribution. In addition to exact inference, we use thisencoding to implement an MCMC algorithm that explores the space of orbitsquickly by uniform orbit sampling.