Efficient Detection of Commutative Factors in Factor Graphs

Malte Luttermann, Johann Machemer, Marcel Gehrke
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:38-56, 2024.

Abstract

Lifted probabilistic inference exploits symmetries in probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state-of-the-art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor’s arguments, i.e., O($2^n$) iterations for a factor with n arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-luttermann24a, title = {Efficient Detection of Commutative Factors in Factor Graphs}, author = {Luttermann, Malte and Machemer, Johann and Gehrke, Marcel}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {38--56}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/luttermann24a/luttermann24a.pdf}, url = {https://proceedings.mlr.press/v246/luttermann24a.html}, abstract = {Lifted probabilistic inference exploits symmetries in probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state-of-the-art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor’s arguments, i.e., O($2^n$) iterations for a factor with n arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.} }
Endnote
%0 Conference Paper %T Efficient Detection of Commutative Factors in Factor Graphs %A Malte Luttermann %A Johann Machemer %A Marcel Gehrke %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-luttermann24a %I PMLR %P 38--56 %U https://proceedings.mlr.press/v246/luttermann24a.html %V 246 %X Lifted probabilistic inference exploits symmetries in probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state-of-the-art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor’s arguments, i.e., O($2^n$) iterations for a factor with n arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.
APA
Luttermann, M., Machemer, J. & Gehrke, M.. (2024). Efficient Detection of Commutative Factors in Factor Graphs. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:38-56 Available from https://proceedings.mlr.press/v246/luttermann24a.html.

Related Material