Effective greedy Boolean matrix factorization via the Rice-Siff algorithm

Effective greedy Boolean matrix factorization via the Rice-Siff algorithm

Authors

Lubomir Antoni , Dominika Kotlárová , Ondrej Krídlo , Domingo López-Rodríguez , Manuel Ojeda-Aciego

Published

15 June 2026

Publication details

International Journal of Approximate Reasoning vol. 197 , pages 109747.

Links

DOI PDF

 

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

How to cite

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.

BibTeX

<pre><code>

@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.}, }

<button class='copy-bib-btn' id='copy-bib-btn'><i class='bi bi-clipboard'></i> Copy BibTeX</button>