Delegation-Relegation for Boolean Matrix Factorization
DOI:
https://doi.org/10.1609/aaai.v38i18.30049Keywords:
SO: Combinatorial Optimization, CSO: Constraint Optimization, CSO: Satisfiability, DMKM: Rule Mining & Pattern MiningAbstract
The Boolean Matrix Factorization (BMF) problem aims to represent a n×m Boolean matrix as the Boolean product of two matrices of small rank k, where the product is computed using Boolean algebra operations. However, finding a BMF of minimum rank is known to be NP-hard, posing challenges for heuristic algorithms and exact approaches in terms of rank found and computation time, particularly as matrix size or the number of entries equal to 1 grows. In this paper, we present a new approach to simplifying the matrix to be factorized by reducing the number of 1-entries, which allows to directly recover a Boolean factorization of the original matrix from its simplified version. We introduce two types of simplification: one that performs numerous simplifications without preserving the original rank and another that performs fewer simplifications but guarantees that an optimal BMF on the simplified matrix yields an optimal BMF on the original matrix. Furthermore, our experiments show that our approach outperforms existing exact BMF algorithms.Downloads
Published
2024-03-24
How to Cite
Avellaneda, F., & Villemaire, R. (2024). Delegation-Relegation for Boolean Matrix Factorization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18), 20632-20639. https://doi.org/10.1609/aaai.v38i18.30049
Issue
Section
AAAI Technical Track on Search and Optimization