Lifted Model Construction Without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs

Malte Luttermann, Ralf Möller, Marcel Gehrke
Proceedings of the Third Learning on Graphs Conference, PMLR 269:46:1-46:17, 2025.

Abstract

Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes of logical variables. We found that the current state-of-the-art algorithm to construct a lifted representation in form of a parametric factor graph misses symmetries between factors that are exchangeable but scaled differently, thereby leading to a less compact representation. In this paper, we propose a generalisation of the advanced colour passing (ACP) algorithm, which is the state of the art to construct a parametric factor graph. Our proposed algorithm allows for potentials of factors to be scaled arbitrarily and efficiently detects more symmetries than the original ACP algorithm. By detecting strictly more symmetries than ACP, our algorithm significantly reduces online query times for probabilistic inference when the resulting model is applied, which we also confirm in our experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v269-luttermann25a, title = {Lifted Model Construction Without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs}, author = {Luttermann, Malte and M{\"o}ller, Ralf and Gehrke, Marcel}, booktitle = {Proceedings of the Third Learning on Graphs Conference}, pages = {46:1--46:17}, year = {2025}, editor = {Wolf, Guy and Krishnaswamy, Smita}, volume = {269}, series = {Proceedings of Machine Learning Research}, month = {26--29 Nov}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v269/main/assets/luttermann25a/luttermann25a.pdf}, url = {https://proceedings.mlr.press/v269/luttermann25a.html}, abstract = {Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes of logical variables. We found that the current state-of-the-art algorithm to construct a lifted representation in form of a parametric factor graph misses symmetries between factors that are exchangeable but scaled differently, thereby leading to a less compact representation. In this paper, we propose a generalisation of the advanced colour passing (ACP) algorithm, which is the state of the art to construct a parametric factor graph. Our proposed algorithm allows for potentials of factors to be scaled arbitrarily and efficiently detects more symmetries than the original ACP algorithm. By detecting strictly more symmetries than ACP, our algorithm significantly reduces online query times for probabilistic inference when the resulting model is applied, which we also confirm in our experiments.} }
Endnote
%0 Conference Paper %T Lifted Model Construction Without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs %A Malte Luttermann %A Ralf Möller %A Marcel Gehrke %B Proceedings of the Third Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2025 %E Guy Wolf %E Smita Krishnaswamy %F pmlr-v269-luttermann25a %I PMLR %P 46:1--46:17 %U https://proceedings.mlr.press/v269/luttermann25a.html %V 269 %X Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes of logical variables. We found that the current state-of-the-art algorithm to construct a lifted representation in form of a parametric factor graph misses symmetries between factors that are exchangeable but scaled differently, thereby leading to a less compact representation. In this paper, we propose a generalisation of the advanced colour passing (ACP) algorithm, which is the state of the art to construct a parametric factor graph. Our proposed algorithm allows for potentials of factors to be scaled arbitrarily and efficiently detects more symmetries than the original ACP algorithm. By detecting strictly more symmetries than ACP, our algorithm significantly reduces online query times for probabilistic inference when the resulting model is applied, which we also confirm in our experiments.
APA
Luttermann, M., Möller, R. & Gehrke, M.. (2025). Lifted Model Construction Without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs. Proceedings of the Third Learning on Graphs Conference, in Proceedings of Machine Learning Research 269:46:1-46:17 Available from https://proceedings.mlr.press/v269/luttermann25a.html.

Related Material