A key goal in the design of probabilistic inference algorithms is identifying and exploiting properties of the distribution that make inference tractable.Lifted inference algorithms identify symmetry as a property that enables efficient inference and seek to scale with the degree of symmetry of a probability model.A limitation of existing exact lifted inference techniques is that they do not apply to nonrelational representations like factor graphs.In this work we provide the first example of an exact lifted inference algorithm for arbitrary discrete factor graphs.In addition we describe a lifted Markov-Chain Monte-Carlo algorithm that provably mixes rapidly in the degree of symmetry of the distribution.

@inproceedings{HoltzenUAI19,
  author    = {Holtzen, Steven and Millstein, Todd and Van den Broeck, Guy},
  title     = {Generating and Sampling Orbits for Lifted Probabilistic Inference},
  booktitle = {Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI)},
  month     = 7,
  year      = {2019},
  keywords  = {conference,selective},
  url       = "http://starai.cs.ucla.edu/papers/HoltzenUAI19.pdf",
  slides    = "http://starai.cs.ucla.edu/slides/UAI19Holtzen.pdf",
  video     = "https://www.youtube.com/watch?v=ng64n3hsnPI",
  code = "https://github.com/SHoltzen/orbitgen",
  annotation = "(Oral full presentation, acceptance rate 35/450 = 7\%)",
}