Block-Value Symmetries in Probabilistic Graphical Models

Gagan Madan, Ankit Anand,  Mausam, Parag Singla
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:885-894, 2018.

Abstract

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 variablevalue (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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-madan18a, title = {Block-Value Symmetries in Probabilistic Graphical Models}, author = {Madan, Gagan and Anand, Ankit and Mausam and Singla, Parag}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {885--894}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/madan18a/madan18a.pdf}, url = {https://proceedings.mlr.press/r16/madan18a.html}, abstract = {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 variablevalue (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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Block-Value Symmetries in Probabilistic Graphical Models %A Gagan Madan %A Ankit Anand %A Mausam %A Parag Singla %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-madan18a %I PMLR %P 885--894 %U https://proceedings.mlr.press/r16/madan18a.html %V R16 %X 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 variablevalue (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. %Z Reissued by PMLR on 04 October 2026.
APA
Madan, G., Anand, A., Mausam, & Singla, P.. (2018). Block-Value Symmetries in Probabilistic Graphical Models. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:885-894 Available from https://proceedings.mlr.press/r16/madan18a.html. Reissued by PMLR on 04 October 2026.

Related Material