Research map / Learning theory and algorithms / Matrix and tensor methods
Delegation-Relegation for Boolean Matrix Factorization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes delegation/relegation operators that simplify Boolean matrices by replacing redundant 1-entries with missing values, so constraint-based BMF solvers run faster on the reduced matrix while recovering a factorization of the original.
Problem
Boolean matrix factorization (BMF) to find exact factorizations of minimal rank is NP-hard, and exact constraint-based solvers become too slow as matrix size and the number of 1-entries grow.
Approach
Extend the GreEss/Iteress matrix simplification idea to incomplete (don't-care) matrices via row/column inclusion; an existential variant (Simpli∃) removes many 1s but may change rank, while a universal variant (Simpli∀) provably preserves optimal rank, and a relegation step maps factorizations of the simplified matrix back to the original.
Key results
- Simpli∃ yields fewer remaining 1s than Iteress on the classic datasets (e.g. Mushroom 51 vs. Iteress not factorizable; Chess 38 vs 368), and Simpli∀ generally also produces fewer 1s than Iteress.
- With CG, Simpli∀ raises the number of datasets solved to proven optimality from 5 to 11 of 31, and never degrades rank; Simpli∃0 gives best rank on 29 of 31 datasets with often orders-of-magnitude time reductions.
- On synthetic 1000x500 matrices, universal simplification lets UndercoverBMF find optimal BMF in 5s-2h for rank 20-30 where the original matrix did not finish.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| universally simplify the matrix before factorization (ablation) | UndercoverBMF · Synthetic BMF, rank 20, densities 0.1–0.4 | computation time: 5m -> 4s; 14m -> 4s; 20m -> 3s; 30m -> 2s | Helped |
| universally simplify the matrix before factorization (ablation) | UndercoverBMF · Synthetic BMF, rank 30, densities 0.1–0.4 | computation time: 2h -> 1m; 1h -> 4m; 1h -> 8m; 2h -> 4m | Helped |
| universally simplify the matrix before factorization (ablation) | UndercoverBMF · Synthetic BMF, rank 40, densities 0.1–0.3 | computation time: 11m; 54m; 3h | Helped |
| use existential simplification with missing values replaced by zeros (ablation) | CG · Mushroom | computation time: 3h -> 1s | Helped |
| use existential simplification with missing values replaced by zeros (ablation) | CG · Chess | computation time: 3h -> 1s | Helped |
| use existential simplification with missing values replaced by zeros (ablation) | CG · Soybean | rank: 99 -> 88 | Helped |
| universally simplify the matrix (ablation) | CG · Americas-small | rank: 1521 -> 299 | Helped |
| replace existential simplification with universal simplification (ablation) | BMF simplification · Synthetic BMF, rank 40, density 0.4 | remaining 1-entries: 57; 9029 | Mixed |
| use universal rather than existential simplification (ablation) | CG · Synthetic BMF, rank 30, density 0.4 | remaining 1-entries: 2856; 36 | Hurt |
| universally simplify the matrix before factorization (ablation) | CG · 31 classic datasets | optimality proofs: 5 out of 31 -> 11 out of 31 | Helped |
| apply existential simplification with missing values replaced by zeros (ablation) | CG · 31 classic datasets | best rank found: 29 out of 31 | Helped |
| apply existential simplification with missing values replaced by zeros (ablation) | OptiBlock · 31 classic datasets | best rank or resolution time: 25 out of 31 | Helped |
Surprising findings
- Replacing empty entries with zeros after existential simplification (Simpli∃0) rarely degrades rank and often reduces factorization time.
- Simplification also lets heuristic solver OptiBlock find lower-rank factorizations on several datasets.
Limitations
- Existential simplification does not guarantee preserving minimal rank.
- Incomplete matrices cannot be handled by some baselines (Iteress, GreEss), limiting comparisons.
- Gains depend on the downstream solver; evaluated only on CG and OptiBlock.
Experimental setup
Datasets: UCI classic datasets (31 total, e.g. Audiology, Mushroom, Nursery) Ene et al. 2008 role-mining datasets (Americas-small, Apj, Customer) DNA (Myllykangas et al. 2006) Paleo (Zliobaite et al. 2023) synthetic 1000x500 matrices following GreEss protocol
Benchmarks: UCI classic datasets Ene et al. role-mining datasets DNA Paleo synthetic BMF matrices (GreEss protocol)
Metrics: number of remaining 1s after simplification computation time factorization rank found
Baselines: Iteress CG OptiBlock UndercoverBMF
Builds on: GreEss Iteress UndercoverBMF
Closest papers by meaning
- Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent (NeurIPS 2022 · similarity 0.88)
- Federated Binary Matrix Factorization Using Proximal Optimization (AAAI 2025 · similarity 0.86)
- The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.82)
- Computationally Hard Problems Are Hard for QBF Proof Systems Too (AAAI 2025 · similarity 0.81)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.81)
- Online Matrix Completion: A Collaborative Approach with Hott Items (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.