Shapeshifter: A Dynamic Graph-Restructuring Algorithm for Improved Inference in Loopy-Structured PGMs

Katerine M. Sadie, Johan A. du Preez, Willie Brink
Proceedings of the 13th International Conference on Probabilistic Graphical Models, PMLR 343:780-796, 2026.

Abstract

Inference in probabilistic graphical models (PGMs) is sensitive to the choice of graph structure used for message passing. While junction trees allow for exact inference, their use is practically infeasible due to exponential blow-up in cluster sizes. Loopy-structured PGMs, like factor graphs or cluster graphs, are computationally tractable alternatives, but the gap between the performance of such graphs and the ideal performance of junction trees still exists. We propose "shapeshifter", an algorithm that dynamically restructures a cluster graph during inference, by merging cluster pairs based on disagreement and redundancy criteria. We evaluate on two distinct domains: error correction and constraint satisfaction. The results show that shapeshifter offers a practical middle ground: improved inference when compared to existing PGM-based approaches—closing the performance gap by a substantial margin—without the prohibitive computational expense of junction trees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v343-sadie26a, title = {Shapeshifter: A Dynamic Graph-Restructuring Algorithm for Improved Inference in Loopy-Structured PGMs}, author = {Sadie, Katerine M. and {du Preez}, Johan A. and Brink, Willie}, booktitle = {Proceedings of the 13th International Conference on Probabilistic Graphical Models}, pages = {780--796}, year = {2026}, editor = {Camps-Valls, Gustau and Leonelli, Manuele and Varando, Gherardo}, volume = {343}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v343/main/assets/sadie26a/sadie26a.pdf}, url = {https://proceedings.mlr.press/v343/sadie26a.html}, abstract = {Inference in probabilistic graphical models (PGMs) is sensitive to the choice of graph structure used for message passing. While junction trees allow for exact inference, their use is practically infeasible due to exponential blow-up in cluster sizes. Loopy-structured PGMs, like factor graphs or cluster graphs, are computationally tractable alternatives, but the gap between the performance of such graphs and the ideal performance of junction trees still exists. We propose "shapeshifter", an algorithm that dynamically restructures a cluster graph during inference, by merging cluster pairs based on disagreement and redundancy criteria. We evaluate on two distinct domains: error correction and constraint satisfaction. The results show that shapeshifter offers a practical middle ground: improved inference when compared to existing PGM-based approaches—closing the performance gap by a substantial margin—without the prohibitive computational expense of junction trees.} }
Endnote
%0 Conference Paper %T Shapeshifter: A Dynamic Graph-Restructuring Algorithm for Improved Inference in Loopy-Structured PGMs %A Katerine M. Sadie %A Johan A. du Preez %A Willie Brink %B Proceedings of the 13th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2026 %E Gustau Camps-Valls %E Manuele Leonelli %E Gherardo Varando %F pmlr-v343-sadie26a %I PMLR %P 780--796 %U https://proceedings.mlr.press/v343/sadie26a.html %V 343 %X Inference in probabilistic graphical models (PGMs) is sensitive to the choice of graph structure used for message passing. While junction trees allow for exact inference, their use is practically infeasible due to exponential blow-up in cluster sizes. Loopy-structured PGMs, like factor graphs or cluster graphs, are computationally tractable alternatives, but the gap between the performance of such graphs and the ideal performance of junction trees still exists. We propose "shapeshifter", an algorithm that dynamically restructures a cluster graph during inference, by merging cluster pairs based on disagreement and redundancy criteria. We evaluate on two distinct domains: error correction and constraint satisfaction. The results show that shapeshifter offers a practical middle ground: improved inference when compared to existing PGM-based approaches—closing the performance gap by a substantial margin—without the prohibitive computational expense of junction trees.
APA
Sadie, K.M., du Preez, J.A. & Brink, W.. (2026). Shapeshifter: A Dynamic Graph-Restructuring Algorithm for Improved Inference in Loopy-Structured PGMs. Proceedings of the 13th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 343:780-796 Available from https://proceedings.mlr.press/v343/sadie26a.html.

Related Material