Skip to content
conftrace_
2026 PGM PGM 2026

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

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.

More from PGM 2026

All PGM 2026 papers →