Automorphism Groups of Graphical Models and Lifted Variational Inference

Hung Bui, Tuyen Huynh, Sebasitan Riedel
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:55-64, 2013.

Abstract

Using the theory of group action, we first in- troduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symme- try of a probabilistic model. This automorphism group provides a precise mathematical frame- work for lifted inference in the general exponen- tial family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of com- puting marginals or expectations for each class, thus avoiding the need to deal with each individ- ual variable or feature. We demonstrate the use- fulness of this general framework in lifting two classes of variational approximation for maxi- mum a posteriori (MAP) inference: local linear programming (LP) relaxation and local LP re- laxation with cycle constraints; the latter yields the first lifted variational inference algorithm that operates on a bound tighter than the local con- straints.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-bui13a, title = {Automorphism Groups of Graphical Models and Lifted Variational Inference}, author = {Bui, Hung and Huynh, Tuyen and Riedel, Sebasitan}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {55--64}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/bui13a/bui13a.pdf}, url = {https://proceedings.mlr.press/r11/bui13a.html}, abstract = {Using the theory of group action, we first in- troduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symme- try of a probabilistic model. This automorphism group provides a precise mathematical frame- work for lifted inference in the general exponen- tial family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of com- puting marginals or expectations for each class, thus avoiding the need to deal with each individ- ual variable or feature. We demonstrate the use- fulness of this general framework in lifting two classes of variational approximation for maxi- mum a posteriori (MAP) inference: local linear programming (LP) relaxation and local LP re- laxation with cycle constraints; the latter yields the first lifted variational inference algorithm that operates on a bound tighter than the local con- straints.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Automorphism Groups of Graphical Models and Lifted Variational Inference %A Hung Bui %A Tuyen Huynh %A Sebasitan Riedel %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-bui13a %I PMLR %P 55--64 %U https://proceedings.mlr.press/r11/bui13a.html %V R11 %X Using the theory of group action, we first in- troduce the concept of the automorphism group of an exponential family or a graphical model, thus formalizing the general notion of symme- try of a probabilistic model. This automorphism group provides a precise mathematical frame- work for lifted inference in the general exponen- tial family. Its group action partitions the set of random variables and feature functions into equivalent classes (called orbits) having identical marginals and expectations. Then the inference problem is effectively reduced to that of com- puting marginals or expectations for each class, thus avoiding the need to deal with each individ- ual variable or feature. We demonstrate the use- fulness of this general framework in lifting two classes of variational approximation for maxi- mum a posteriori (MAP) inference: local linear programming (LP) relaxation and local LP re- laxation with cycle constraints; the latter yields the first lifted variational inference algorithm that operates on a bound tighter than the local con- straints. %Z Reissued by PMLR on 04 October 2026.
APA
Bui, H., Huynh, T. & Riedel, S.. (2013). Automorphism Groups of Graphical Models and Lifted Variational Inference. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:55-64 Available from https://proceedings.mlr.press/r11/bui13a.html. Reissued by PMLR on 04 October 2026.

Related Material