# Graph Coloring: Comparing Cluster Graphs to Factor Graphs

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

## Key facts

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

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

- [Join-Graph Propagation Algorithms](https://mlsanity.com/paper/1401.3489/) (2014)

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

- [A Temporal Extension of Latent Dirichlet Allocation for Unsupervised Acoustic Unit Discovery](https://mlsanity.com/paper/2206.11706/) (2022)
- [SimLDA: A tool for topic model evaluation](https://mlsanity.com/paper/2208.09299/) (2022)
- [LDPC codes: comparing cluster graphs to factor graphs](https://mlsanity.com/paper/2204.06350/) (2022)
- [LDPC codes: tracking non-stationary channel noise using sequential variational Bayesian estimates](https://mlsanity.com/paper/2204.07037/) (2022)

## Abstract (arXiv)

We present a means of formulating and solving graph coloring problems with probabilistic graphical models. In contrast to the prevalent literature that uses factor graphs for this purpose, we instead approach it from a cluster graph perspective. Since there seems to be a lack of algorithms to automatically construct valid cluster graphs, we provide such an algorithm (termed LTRIP). Our experiments indicate a significant advantage for preferring cluster graphs over factor graphs, both in terms of accuracy as well as computational efficiency.