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 proba- bilistic graphical models is to first merge sym- metric 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 us- ing 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 sym- metries, and can compute many more sym- metries for increasing block sizes. To opera- tionalize use of BV permutations in lifted in- ference, we describe 1) an algorithm to com- pute BV permutations given a block parti- tion of the variables, 2) BV-MCMC, an exten- sion 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 proba- bilistic graphical models is to first merge sym- metric 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 us- ing 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 sym- metries, and can compute many more sym- metries for increasing block sizes. To opera- tionalize use of BV permutations in lifted in- ference, we describe 1) an algorithm to com- pute BV permutations given a block parti- tion of the variables, 2) BV-MCMC, an exten- sion 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 proba- bilistic graphical models is to first merge sym- metric 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 us- ing 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 sym- metries, and can compute many more sym- metries for increasing block sizes. To opera- tionalize use of BV permutations in lifted in- ference, we describe 1) an algorithm to com- pute BV permutations given a block parti- tion of the variables, 2) BV-MCMC, an exten- sion 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