Undercover Boolean Matrix Factorization with MaxSAT


  • Florent Avellaneda Université du Québec à Montréal Centre de Recherche de l'Institut Universitaire de Gériatrie de Montréal
  • Roger Villemaire Université du Québec à Montréal




Constraint Satisfaction And Optimization (CSO), Search And Optimization (SO), Knowledge Representation And Reasoning (KRR)


The k-undercover Boolean matrix factorization problem aims to approximate a m×n Boolean matrix X as the Boolean product of an m×k and a k×n matrices A◦B such that X is a cover of A◦B, i.e., no representation error is allowed on the 0’s entries of the matrix X. To infer an optimal and “block-optimal” k-undercover, we propose two exact methods based on MaxSAT encodings. From a theoretical standpoint, we prove that our method of inferring “block-optimal” k-undercover is a (1 - 1/e) ≈ 0.632 approximation for the optimal k-undercover problem. From a practical standpoint, experimental results indicate that our “block-optimal” k-undercover algorithm outperforms the state-of-the-art even when compared with algorithms for the more general k-undercover Boolean Matrix Factorization problem for which only minimizing reconstruction error is required.




How to Cite

Avellaneda, F., & Villemaire, R. (2022). Undercover Boolean Matrix Factorization with MaxSAT. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3672-3681. https://doi.org/10.1609/aaai.v36i4.20280



AAAI Technical Track on Constraint Satisfaction and Optimization