# Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm

arXiv: https://arxiv.org/abs/2110.00091 · HTML: https://mlsanity.com/paper/2110.00091/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 42 references that are in the map.
- First posted on arXiv 30 Sep 2021.

## Builds on (most cited first, 1 of 1)

- [Pattern-Based Constraint Satisfaction and Logic Puzzles](https://mlsanity.com/paper/1304.1628/) (2013)

## Built on by (most cited first, 3 of 3)

- [SimLDA: A tool for topic model evaluation](https://mlsanity.com/paper/2208.09299/) (2022)
- [A derivation of variational message passing (VMP) for latent Dirichlet allocation (LDA)](https://mlsanity.com/paper/2111.01480/) (2021)
- [LDPC codes: comparing cluster graphs to factor graphs](https://mlsanity.com/paper/2204.06350/) (2022)

## Abstract (arXiv)

Probabilistic graphical models (PGMs) are powerful tools for solving systems of complex relationships over a variety of probability distributions. However, while tree-structured PGMs always result in efficient and exact solutions, inference on graph (or loopy) structured PGMs is not guaranteed to discover the optimal solutions. It is in principle possible to convert loopy PGMs to an equivalent tree structure, but this is usually impractical for interesting problems due to exponential blow-up. To address this, we developed the purge-and-merge algorithm. This algorithm iteratively nudges a malleable graph structure towards a tree structure by selectively merging factors. The merging process is designed to avoid exponential blow-up by way of sparse structures from which redundancy is purged as the algorithm progresses. We set up tasks to test the algorithm on constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro, and it outperformed other PGM-based approaches reported in the literature. While the tasks we set focussed on the binary logic of CSP, we believe the purge-and-merge algorithm could be extended to general PGM inference.