# Boolean Matrix Factorization and Noisy Completion via Message Passing

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2015.

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

- [Structured Neural Networks for Density Estimation and Causal Inference](https://mlsanity.com/paper/2311.02221/) (2023)
- [ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspective](https://mlsanity.com/paper/2207.09980/) (2022)
- [PGMax: Factor Graphs for Discrete Probabilistic Graphical Models and Loopy Belief Propagation in JAX](https://mlsanity.com/paper/2202.04110/) (2022)
- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent](https://mlsanity.com/paper/2307.07615/) (2023)
- [Learning noisy-OR Bayesian Networks with Max-Product Belief Propagation](https://mlsanity.com/paper/2302.00099/) (2023)
- [Topic Modeling and Link-Prediction for Material Property Discovery](https://mlsanity.com/paper/2507.06139/) (2025)
- [Adaptive Data-Knowledge Alignment in Genetic Perturbation Prediction](https://mlsanity.com/paper/2510.00512/) (2025)
- [Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics](https://mlsanity.com/paper/2512.03807/) (2025)
- [A Bayesian Boolean Matrix Factorization with Application to Copy Number Analysis in Cancer](https://mlsanity.com/paper/2606.17491/) (2026)

## Abstract (arXiv)

Boolean matrix factorization and Boolean matrix completion from noisy observations are desirable unsupervised data-analysis methods due to their interpretability, but hard to perform due to their NP-hardness. We treat these problems as maximum a posteriori inference problems in a graphical model and present a message passing approach that scales linearly with the number of observations and factors. Our empirical study demonstrates that message passing is able to recover low-rank Boolean matrices, in the boundaries of theoretically possible recovery and compares favorably with state-of-the-art in real-world applications, such collaborative filtering with large-scale Boolean data.