Delegation-Relegation for Boolean Matrix Factorization

Florent Avellaneda, Roger VillemaireAAAI 2024 · DOI

Introduction

Boolean Matrix Factorization (BMF) is a fundamental task in data mining, aiming to decompose a binary matrix $X$ into two smaller binary matrices $A$ and $B$ such that $X \approx A \circ B$ under Boolean algebra (where $1+1=1$). This technique is widely applied in fields ranging from bioinformatics and security to logic synthesis, as it excels at uncovering latent patterns in binary data.

However, finding the "minimal rank"—the smallest inner dimension for $A$ and $B$—is an NP-hard problem. While heuristic algorithms are commonly used, they often fail to find optimal solutions. Conversely, exact solvers based on constraint programming (such as SAT or Mixed-Integer Programming) can find optimal results but are severely limited by the density of 1-entries in the input matrix. As the number of 1s grows, these solvers often hit a computational "wall." This paper introduces the Delegation-Relegation framework, a preprocessing technique designed to overcome this bottleneck by strategically simplifying the input matrix.

The Delegation-Relegation Framework

The core idea of the framework is to reduce the number of 1-entries that an exact solver must account for by exploiting redundancies in the data. The process consists of two primary phases: Delegation and Relegation.

1. Delegation (Simplification)

In the delegation phase, the algorithm identifies rows or columns that are "included" in others. If a row $v$ is a subset of another row $w$, many of the 1s in $v$ can be "delegated" to $w$. These 1s are then replaced with either 0s or "don't care" values ($\emptyset$). This conversion is crucial because, in BMF, every 1 must be covered by at least one rank-1 submatrix (a "block"). By introducing $\emptyset$ values, the solver gains the flexibility to either cover the entry or ignore it, significantly pruning the search space.

Visualizing the delegation process where 1-entries are replaced by 'don't care' values or zeros based on row inclusion.

The authors propose two variants of this approach:

  • Universal Inclusion (Simpli$^\forall$): A conservative method that guarantees the optimal rank of the simplified matrix remains identical to the original.
  • Existential Inclusion (Simpli$^\exists$): A more aggressive approach that removes more 1s. While it lacks the strict rank-preservation guarantee of the universal variant, it often results in faster solve times and lower ranks in practical applications.

2. Relegation (Reconstruction)

Once an external solver has factorized the simplified matrix, the "relegation" operator is applied. This mathematical step maps the solution back to the original matrix dimensions, ensuring that the final factorization is a valid representation of the unsimplified data.

Experimental Evaluation

The researchers evaluated the framework using two exact solvers—Column Generation (CG) and OptiBlock—across 31 classic datasets from the UCI Machine Learning Repository and various synthetic benchmarks. The goal was to measure the impact of simplification on both the number of 1-entries and the total computation time.

Key Results and Speedups

The empirical results demonstrate that Delegation-Relegation provides orders-of-magnitude improvements in efficiency. For instance, in the "Advert" dataset, the number of 1-entries was reduced from 45,139 to just 705 using the Simpli$^\exists$ method.

Comparative performance of BMF solvers on various datasets, showing significant reductions in 1-entries and computation time after simplification.

As shown in the table above, the speedups are dramatic. For the "Americ" dataset, the standard CG solver failed to find a solution within a 3-hour limit. However, after applying Simpli$^\exists$ preprocessing, the solver reached a solution in just 2 minutes. Furthermore, because the simplified matrices are easier to process, solvers frequently found lower-rank factorizations than they could on the original data within the same time constraints. In the "APJ" dataset, the discovered rank dropped from 1148 to 453.

Conclusion

The Delegation-Relegation framework represents a significant step forward for exact Boolean Matrix Factorization. By treating redundancy as an opportunity for sparsification rather than a burden, the method allows exact solvers to handle much larger and denser datasets than previously possible. Future work will focus on optimizing the greedy ordering of the delegation process and extending the framework to handle approximate BMF, where a predefined level of error is acceptable.

Summary updated

BibTeX
@inproceedings{avellaneda2024delegation,
  author = {Florent Avellaneda and Roger Villemaire},
  title = {{Delegation-Relegation for Boolean Matrix Factorization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30049},
}
Figure