Effective greedy Boolean matrix factorization via the Rice-Siff algorithm

 

Abstract

This paper introduces a new Boolean Matrix Factorization (BMF) algorithm based on the Rice-Siff agglomerative clustering method. Our approach, Rice-Siff Factorization (RSF), integrates a greedy set-cover framework, where formal concepts serve as interpretable factors, with a dynamic candidate-generation process. By incorporating optimized variants such as RSF with Early Stopping (RSF-ES), we propose a pruning criterion based on order-theoretic properties to detect redundant candidates and significantly enhance factor extraction. Extensive synthetic benchmarks and experiments on real-world datasets demonstrate the effectiveness and robustness of the proposed framework, showing that RSF-ES provides significant scalability gains, yielding speedups on high-dimensional datasets with thousands of attributes while maintaining mathematical exactness. A comprehensive comparison with established factorization algorithms and an analysis of its theoretical properties show that RSF-ES represents a highly efficient and scalable solution for Boolean data analysis.

Funding

NoteProjects funding this work

Citation

Please, cite this work as:

[Ant+26] L. Antoni, D. Kotlárová, O. Krídlo, et al. “Effective greedy Boolean matrix factorization via the Rice-Siff algorithm”. In: International Journal of Approximate Reasoning 197 (2026), p. 109747. ISSN: 0888-613X. DOI: https://doi.org/10.1016/j.ijar.2026.109747. URL: https://www.sciencedirect.com/science/article/pii/S0888613X26001222.

NoteBibTeX

@Article{ANTONI2026109747,
     title = {Effective greedy Boolean matrix factorization via the Rice-Siff algorithm},
     journal = {International Journal of Approximate Reasoning},
     volume = {197},
     pages = {109747},
     year = {2026},
     issn = {0888-613X},
     doi = {https://doi.org/10.1016/j.ijar.2026.109747},
     url = {https://www.sciencedirect.com/science/article/pii/S0888613X26001222},
     author = {Lubomir Antoni and Dominika Kotl{‘a}rov{’a} and Ondrej Kr{’}dlo and Domingo L{‘o}pez-Rodr{’}guez and Manuel Ojeda-Aciego},
     keywords = {Boolean matrix decomposition, Formal context factorisation, Greedy algorithm},
     abstract = {This paper introduces a new Boolean Matrix Factorization (BMF) algorithm based on the Rice-Siff agglomerative clustering method. Our approach, Rice-Siff Factorization (RSF), integrates a greedy set-cover framework, where formal concepts serve as interpretable factors, with a dynamic candidate-generation process. By incorporating optimized variants such as RSF with Early Stopping (RSF-ES), we propose a pruning criterion based on order-theoretic properties to detect redundant candidates and significantly enhance factor extraction. Extensive synthetic benchmarks and experiments on real-world datasets demonstrate the effectiveness and robustness of the proposed framework, showing that RSF-ES provides significant scalability gains, yielding speedups on high-dimensional datasets with thousands of attributes while maintaining mathematical exactness. A comprehensive comparison with established factorization algorithms and an analysis of its theoretical properties show that RSF-ES represents a highly efficient and scalable solution for Boolean data analysis.},
}