Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent
Authors: Sebastian Dalleiger
Jilles Vreeken
Venue: NeurIPS 2022 Accept (2022)
Keywords: Boolean Matrix Factorization
Non-negative Matrix Factorization
Proximal Point
Elastic Net
Model Selection

Abstract: Addressing the interpretability problem of NMF on Boolean data, Boolean Matrix Factorization (BMF) uses Boolean algebra to decompose the input into low-rank Boolean factor matrices. These matrices are highly interpretable and very useful in practice, but they come at the high computational cost of solving an NP-hard combinatorial optimization problem. To reduce the computational burden, we propose to relax BMF continuously using a novel elastic-binary regularizer, from which we derive a proximal gradient algorithm. Through an extensive set of experiments, we demonstrate that our method works well in practice: On synthetic data, we show that it converges quickly, recovers the ground truth precisely, and estimates the simulated rank exactly. On real-world data, we improve upon the state of the art in recall, loss, and runtime, and a case study from the medical domain confirms that our results are easily interpretable and semantically meaningful.

Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent
Sebastian Dalleiger
Jilles Vreeken
CISPA Helmholtz Center for Information Security rebastian.dalleigeer&eii cispa.
CISPA Helmholtz Center for Information Security jv@cispa.de
Abstract
Addressing the interpretability problem of NMF on Boolean data, Boolean Matrix Factorization (BMF) uses Boolean algebra to decompose the input into low-rank Boolean factor matrices. These matrices are highly interpretable and very useful in practice, but they come at the high computational cost of solving an NP-hard combinatorial optimization problem. To reduce the computational burden, we propose to relax BMF continuously using novel caastic-binary regularizer, from which we derive a proximal gradient algorithm. Through an extensive set of experiments, we demonstrate that our method works well in practice: On synthetic data, we show that it converges quickly, recovers the ground truth precisely, and estimates the simulated rank exactly. On real-world data, we improve upon the state of the art in recall, loss, and runtime, and case study from the medical domain confirms that our results are easily interpretable and semantically meaningful.
Introduction
Discovering groups in data and expressing them in terms of common concepts is central problem in many scientific domains and business applications, including cancer genomics [23], neuroscience [13], and recommender systems [18]. This problem is often addressed using variants of matrix factorization, a family of methods that decompose the target matrix into a set of typically low- rank factor matrices whose product approximates the input well. Prominent examples of matrix factorization are Singular Value Decomposition (SVD) [10], Principal Component Analysis (PCA) [10], and Nonnegative Matrix Factorization (NMF) [31, 21, 22). These methods differ in how they constrain the matrices involved: SVD and PCA require orthogonal factors, while NMF constrains the target matrix and the factors to be nonnegative.
SVD, PCA, and NMF achieve interpretable results-unled the data is Boolean, which is ubiquitous in the real world. In this case, their results are hard to interpret directly because the input domain differs from the output domain, such that post-processing is required to extract useful information. Boolean Matrix Factorization (BMF) addresses this problem by secking two low-rank Boolean factor matrices whose Boolean product is close to the Boolean target matrix [24]. The output matrices, now lying in the same domain as the input, interpretable and useful, but they come the computational cost of solving an Na-hard combinatorial optimization problem [30, 24, 25]. To make BMF applicable in practice, we need efficient approximation algorithms.
There are many ways approximate BMF-for example, by exploiting its underlying combinatorial or spatial structure [24, 6, 5), using probabilistic inference [37, 35, 36), or solving the related Bi- Clustering problem [28, 29]. Although these approaches achieve impressive results, they fall short when the input data is large and noisy. Hence, we take different approach to overcome BMF's computational barrier. Starting from an NMF-like optimization problem, we derive a continuous relaxation of the original BMF formulation that allows intermediate solutions to be real-valued. Inspired by the elastic-net regularizer [43], we introduce the novel elastic binary (ELB) regularizer to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

regularize towards Boolean factor matrices. We obtain an efficient-to-come comopptte proximal operator from our ELB regularizer that projects relaxed real-valued factors towards being Boolean, which allows us to leverage fast gradient-based optimization procedures. In stark contrast to the state of the art [15, 16, 17], which requires heavy post-hoc post-processing to actually achieve Boolean factors, we ensure Boolean outcome upon convergence by gradually increasing the projection strength using a regularization rate. We combine our relaxation, efficient proximal operator, and regularization rate into an Elastic Boolean Matrix Factorization algorithm (ELBMF) that scales to large data, results in accurate reconstructions, and does so without relying on heavy post-processing procedures. ELB and its rate are, however, not confined to BMF and can regularize, e.g., binary MF or bi-clustering [17]. In summary, our main contributions are follows:
1. We introduce the ELB regularizer.
2. We overcome the computational hardness of BMF leveraging a novel relaxed BMF problem.
3. We efficiently solve the relaxed BMF problem using an optimization algorithm based on proximal gradient descent.
The remainder of the paper proceeds follows. In Sec. 2, we formally introduce the BMF problem and its relaxation, define our ELB regularizer and its proximal point operator, and show how to ensure Boolean outcome upon convergence. We discuss related work in Sec. 3, validate our method through an extensive set of experiments Sec. 4, and conclude with a discussion in Sec. 5.
2 Theory
Our goal is to factorize a given Boolean target matrix into at least two smaller, low-rank Boolean factor matrices, whose product comes close to the target matrix. Since the factor matrices are Boolean, this product follows the algebra of Boolean semi-ring. i.e., is identical to the standard outer product on field where addition obeys 1 + +1 1. We define the product between two Boolean matrices {0, 13" 1 and V {0, * on Boolean semi-ring ({0, V,A) as
[U V)g
V VaVi,, [E[M]
where U E 10,1]*** Ve f0, 1] 13 kxm and Uo E {0,1)*X* "x This gives rise to the BMF problem.
Problem (Boolean Matrix Factorization) For given target matrix A E 10,1) given matrix rank N 3 k S min m), and @ B denoting logical exclusive or, discover the factor 1 kxm that minimize
matrices U E {0, 1) j and V E {0, 13
|| Uo ΣAGe
(2)
While beautiful in theory, this problem is NP-complete [25]. Thus, cannot solve this problem exactly for all but the smallest matrices. In practice, we hence have to rely on approximations. Here, relax the Boolean constraints of Eq. (2) to allow non-negative, non-Boolean 'intermediate' factor matrices during the optimization, allowing us to use linear algebra rather than Boolean algebra. In other words, solve the non-negative matrix factorization (NMF) problem [31]
A UVI
subject to E IR* and V R k In contrast to the original BMF formulation, we can solve this problem efficiently, e.g., via a Gauss-Seide scheme. Although efficient, using plain NMF, however, disregards the Boolean structure of our matrices and produces factor matrices from a different domain, which are consequently hard to interpret and potentially very dense. To benefit from efficient optimization and still arrive at Boolean outputs, we allow real-valued intermediate solutions and regularize them towards becoming Boolean.
To steer our optimization towards Boolean solutions, we penalize non-Boolean solutions using regularizer. This idea has been explored in prior work. There exists the l in-inspired PRIMP

---

regularizer [15], which is -x[-|1-- 2x] | + 1] for values inside [0, 1] and oc otherwise, and the 12- inspired bowl-shaped regularizer [42], which X(2² =) everywhere on the real line. Although both have been successfully applied to BMF, both also have undesirable properties: The PRIMP regularizer penalizes well inside the interval [0, 1] but is non-differentiable on the outside, while the bowl-shaped regularizer is differentiable and penalizes well outside the interval [O, 1) but is almost flat on the inside. Hence, both regularizers are problematic used individually. Combining them, however, yields regularizer that penalizes non-Boolean values well across the full real line. To combine 4-- and (g-reuularization, we use the elastic-net regularizer,
r xx) = =||=||| + A||==12
which, however, only penalizes non-zero solutions [43]. To penalize non-Boolean solutions, we combine two elastic-net regularizers into our (almost W-shaped) ELB regularizer,
R(X)= = Σ riie
DEX
where X E (U,V), In Fig. we show all three regularizers in the range of [-1, for == 0.5. We see that only the ELB regularizer penalizes non- non-Boolean solutions across the full spectrum, and summarize regularized relaxed BMF as follows.
Problem 2 (Elastic Boolean Matrix Factorization) For a given target matrix A E {0, 1) and
a given matrix rank N ke S min (,, m). discover the factor matrices Baxk and V E Rkxm that minimize
|| - UV + +R(U) + R(V).
(5)
Although this a relaxed problem, is still non-convex, and therefore, we cannot solve it straightfor- wardly. The problem, however, is suitable for the Gauss-Seidel optimization scheme. That is, we alternatingly fix one factor matrix to optimize the other. By doing so, we generate a sequence
U2+1 arg arggin AA- UV R(C),
(6)
V
V4+1 +- mrg |A- U VII + R(V).
(7)
V
of simpler-to-solve sub-problems, until convergence. Now, each sub-problem is again sum of two f(X) ) + R(() functions, where f is the loss || 11, and R(X) is the regularizer. This allows us follow proximal gradient approach, i.e., we use Proximal Alternating Linear Minimization (PALM) [7, 33]. In nutshell, we minimize a sub- sub-problem by following the gradient V f of f, to then use the proximal operator for R to nudge its outcome towards Boolean solution. That is, for the gradients Vuf = UVV AV and Vv = U UV - U A, we compute the step
prox (X V.),
(8)
where represents the step size, which we compute in terms of Lipschitz constant, rather than relying on costly line-search [7]. To further improve the convergence properties, we make of an inertial term that linearly combines X, with X,-1 before applying Eq. (8) (see [33] for a detailed description).
We now derive the proximal operator for the ELB regularizer, before discussing how we ensure that the factor matrices are Boolean, and summarizing our approach as an algorithm.
2.1 Proximal Mapping
To solve the sub-problem
arg (xx(X) for (x)(X)= -(x) R(X) X
from Eq. (7) for X V), we need proximal operator [32] that projects values towards regularized point. Formalized in Appendix A, in nutshell, this operator is the solution to
pX) = arg min マ || Y 113 + R(X).
(10)
3

---

Regularizer
Algorithm 1: ELBMF
Bowl
Input: Matrix A E {0, 1]axm rank l E EN
0.8
PRIMP
Output: Factors E (0. 1) ma Ve E (0, 13 kxm
R(x)
0.6
ELB
initialize U and V uniformly at random for t 1,2.... until convergence do U + arg reducey bxx, (A, U, V) V <- arg reducey Lnd, (A, U, V)
0.4
0.2
end
return U, V
1
Figure 1: On the left, we show the three regularizers: Bowl, PRIMP, and ELB, for À x= 0.5, and see that only our ELB regularizer penalizes non-Boolean values well. On the right, we show our method ELBMF pseudocode.
As Eq. (10) is coordinate-wise solvable, reduce this equation scalar proximal operator
1 7(x y)² + R(y)
Frox (x) = arg min
(11)
PER 2
Although this scalar function may seem simple, due to R. it non-convex, which in general rulees out the existence of unique minima. We can, however, exploit the W-shape of R. That is, from the perspective of a fixed Xıj. the regularizer locally convex after a case distinction. Starting with the case of X,j = z, I 2 we can simplify Eq. (11) to (2 y)² + X2yy222 + klyl, letting X 2A. Setting its derivative 0, we get to y x x sign(y). Asserting that least-squares solution will always be of the same sign, we substitute the sign of x with sign(y). Repeating these steps analogously for 1/2, we obtain our proximal operator:
Definition 1 (Proximal Operator) Given regularization coefficients k and X proximal operator for matrix X is , = [prox,2> (Xi,)las, where prox,> is the scalar proximal operator
sign (x) prox (x) = (1+ +) 1)-1 x K sign (a 1) +
if S otherwise
(12)
Although not strictly necessary, to improve the empirical convergence rate, we would like to constrain factor matrices to be non-negative. As our proximal operator does not account for this, impose non-negativity by using the alternating projection procedure to combine the non- non-negativity proximal operator [32] with Eq. (12) into max (0, prox, (z)].
2.2 Ensuring Boolean Factors
Our proximal operator only nudges the factor matrices towards becoming Boolean. We, however, want to ensure that our results are Boolean. To this end, the state-of-the-are method PRIMP relies heavily on post-processing, performing very expensive joint two-dimensional grid search to guess the 'best' pair of rounding thresholds, which are then used to produce Boolean matrices. Although this tends to work in practice, it is an inefficient post-hoc procedure- and thus, would be highly desirable to have Boolean factors already upon convergence. To achieve this without rounding or clamping, revisit our regularizer, which binarizes more strongly if we regularize more aggressively. Consequently, if we regularize too aggressively, we converge to a suboptimal solution, and if we regularize too mildly, our output, we start with a weak regularization and gradually increase its strength.
do not binarize our solutions. To prevent subpar solutions and still binarize
Considering Eq. (12), we see that higher regularization strength increases the distance over which our proximal operator projects. Thus, we set the 1 -ddistance controlling k too high, we will immediately leap to Boolean factor matrix, which will terminate the algorithm and yield suboptimal solution.

---

Regulating the l2-distance controlling À is less delicate matter. Hence, we gradually increase À to prevent subpar solution and achieve Boolean outcome, using regularization rate
A x for Vt 2 0 Vt 2 0
(13)
that gradually increases the proximal distance at a user-defined rate. In case ELBMF has stopped without convergence, bridge the remaining integrality gap by projecting the outcome onto its closed Boolean counterpart, using our proximal operator (see Fig. 2).
We summarize the considcrations laid out above ELBMF in Alg. 1. The computational complexity of ELBMF is bounded by the complexity of computing the gradient, which is identical to the complexity of matrix multiplication. Therefore, for all practical purposes, ELBMF is sub-cubic O (n288077 using Strassen's algorithm.
Related Work
Matrix facttrizaaiin is a well-established family of methods, whose members, such as SVD, PCA, or NMF, are used everywhere in machine learning. Almost all matrix factorization methods operate on real-valued matrices, however, while BMF operates under Boolean algebra. Boolean Matrix Factorization originated in the combinatorics community [27] and was later introduced to the data mining community [24], where many cover-based BMF algorithms were developed [6, 5, 24, 26]. In recent years, BMF has gained traction in the machine learning community, which tends tackle the problem differently. Here. relaxation-basse
approaches that optimize for a relaxed but regular- ized BMF [15. 14, 42] are related to our method, but they differ especially in their regularization. Hess et al. [15] introduce a regularizer that is only partially differentiable, and they rely heavily on post-processing to force Boolean solution, and Zhang et al. [42] regularize only weakly between O and 1. In contrast, our regularizer penalizes well across the full spectrum and yields Boolean outcome upon convergence. Building on a thresholding- also consider relaxations to benefit from gradient-based optimization. Other recent approaches build on probabilistic inference. Rukat al. [37, 35, 36], for example, combine Bayesian Modeling and sampling into their logical factor machine. A similar direction is taken by Ravanbakhsh et al. [34], who use graphical models and message passing, and Liang et al. [23]. who combine MAP-inference and sampling. A different, geometry-basse approach lies in locating dense submatrices by ordering the data to exploit the consecutive-one property [40, 38]. Since BMF is essentially solving bipartite graph partitioning problem, it is also closely related Bi-Clustering and Co- Co-Clustering [28, 17). Neumann and Miettinen [29] use this relationship to efficiently solve BMF by means a streaming algorithm. Although there are many different approaches to BMF, its biggest challenge date remains scalability [25].
BMF formulation, Araujo et al. [3]
Experiments
We implement ELBMF in the Julia language and run experiments on 16 Cores of an AMD EPYC 7702 and single NVIDIA A100 GPU, reporting wall-clock time. We provide the source code, datasets, synthetic dataset generator, and other information needed for reproducibility! We compare ELBMF against six methods: four dedicated BMF methods (Asso [24], GRECOND [6], ORM [35], and PRIMP [15]), one streaming Bi- Bi-Clustering algorithm SOFA [29], one elastic-net net-regularized NMF method leveraging proximal gradient descent (NMF [31, 21, 22]), and one interpretable Boolean autoencoder (BINAPS [9)). Since NMF outputs nen-negative factor matrices, rather Boolean matrices, we cannot compare against NMF directly. so we clamp and round solutions to the nearest Boolean outcome. To fairly compare against BINAPS, we task it with autoencoding the target matrix reconstruction, given the matrix ranks from our experiments as the number of latent dimensions. We perform three sets of experiments. First, we ascertain that ELBMF works reliably synthetic data. Second, we verify that it generally performs well on real-world data. And third, we illustrate that its outputs are semantically meaningful through exploratory analysis of biomedical dataset.
4.1 Performance of ELBMF on Synthetic Data
In the following experiments, ask four questions: (1) How does ELBMF converge?: (2) How well does ELBMM recover the information in the target matrix?; (3) How consistently does ELBMF
Appendix C; DOI: 10.5281/2eeooe 771770
5

---

0.5
0.2
0.4
Rate Constant
20,000
keeps changing
Loss Gop
15,000
Boolean
0.1
Hipped
Jar ronserged
0.2
5,000
0.0
1000
Iteration &
Iteration
lieration É
Our method converges quickly under a regularization rate. We report the progression over time of the Boolean gap, loss gap, and the Hamming process, for 1 000 iterations of ELBMF synthetic 400 x 300 matrices with 10% noise and 5 random tiles covering between 50 and 100 rows columns, under constant regularization of A
Figure 2:
regularization rate of X 1.05'.
reconstruct low- or high-density target matrices?; and (4) Does ELBMF estimate the underlying Boolean matrix rank correctly? To answer these questions, we generate synthetic data with known ground truth as follows. Starting with an all-zeros matrix, we randomly create rectangular, non- overlapping, consecutive areas of ones called tiles, each spanning randomly chosen number of consecutive rows and columns, thus inducing matrices with varying densities. We then add noise by setting each cell to uniformly at random, with varying noise probabilities.
How does ELBMF converge? To study how our method converges to Boolean solution, we quantify relevant properties of the sequence of intermediate solutions (cf. Eq. (7)). First, to understand how quickly and stably ELBMF converges Boolean solution, we quantify the Boolean gap,
Σ
|X| 1
Σ min xEX
1[}
XE(U,,V
Second, to understand when can safely round intermediate almost-Boolean solutions without losing information, we calculate, for the reconstruction from rounded intermediate factors, the cumulative Hamming process as the sum of fraction of bits that flip from iteration t to iteration t + 1,
|| - B4t1lli,
and the loss gap the difference between the relaxed loss and the loss from the rounded B.
As shown in Fig. 2, we achieve an almost-Boolcan solution without any rounding after around 250 epochs, continuing until reach Boolean outcome. This is also the point at which the rounded intermediate solution and its relaxation are almost identical, as illustrated by the loss gap. Considering the Hamming process the right, we observe that ELBBF goes through in the beginning, followed by only minor changes each iteration until iteration = 100. Afterwards, regularization rate. When using constant regularization
erratic bit-flipping-hhe
ELBMF has settled solution-une under instead, we continue to observe bit flips until the end of the experiment. Under constant regularization, the Boolean gap hardly decreases over time. Far from Boolean, the constant regularization thus also never closes the loss gap, which is unsurprising, given that its factors are less regularized. In other words, our regularization works well, and allows to safely binarize almost-converged factors that are e-far from being Boolean by means of, e.g.. our proximal operator.
How well does ELBMF recover the information in the target matrix? Having ensured that our method converges stably and quickly, we would like to assess whether it also converges to high-quality factorization. To this end, we generate synthetic 40 30 matrices containing 5 random tiles each spanning 5 to 10 rows and columns, under additive noise levels between 0% (no noise) and 50%. We then compute the fraction of ones target A that is covered by the reconstruction B = Uo V, i.e., the recall (higher is better)
|AI | O B|I1.
(14)
To ensure that we fit the signal the data, we additionally report the recall regarding the generating, foise-free ground-truth tiles A", denoted recall". Finally, to rate the overall reconstruction quality

---

Asso
0.8
0.8
0.8
O GRECOND
Similarit
0
Rocall
Recall
0.4
0.4
0.4
BINAPS
+ NMP
ELaMY
0.2 0.4 0.5
0.3 0.5
0.1 0.3 0.5
Noise
Noise
Noise
Figure 3: Overall, ELBMF reconstructs the noisy synthetic data well and recovers the ground-truth tiles. On synthetic data for additive noise levels increasing from 0% to 50%, we show mean line and standard deviation as shade of similarity, recall w.r.. the target matrix, and recall" w.r.t. the noise-free ground-truth tiles, for Asso, GRECOND, ORM, SOFA, BINAPS, NMF, PRIMP, and ELBMF.
* Asso
0.8
0.8
Relative Loss
0.8
D GiucOnn
Similarit
0.6
Recall
0.6
O&M
SOFA
0.4
0.4
0.4
BINAPS
+ PRIMP
0.2
0.2
ELBMF
0.2
0.4
0.6
0
0.2
0.4
0.6
0.2
0.4
0.6
Density
Density
Density
Figure 4: ELBMF reconstructs noisy synthetic high-density and low-density matrices consistently well. On synthetic data with fixed additive noise, and increasing density, show mean as line and standard deviation as shade of similarity, recall, and relative loss, for BINAPS, Asso, GRECOND, ORM, SOFA, BINAPS, NMF, PRIMP, and ELBMF.
including zeros, we compute the Hamming similarity (higher is better) between the target matrix and its reconstruction
||| BlI1
We run each method on our synthetic datasets, targeting matrix rank 5. account for random fluctuations, we average over 10 randomly drawn sets of 5 ground-truth tiles per 10% increment in noise probability. In Fig. 3, we show similarity, recall, and recall". We observe that in the noiseless case (0%), all methods except BINAPS recover the 5 ground-truth tiles with high accuracy, but only Asso and ELBMF so with perfect recalls. Starting with as little as 10% noise, both recalls of Asso, GRECOND, SOFA, NMF, and BINAPS deteriorate quickly, while the similarity and both recalls of PRIMP and ELBMF remain high. fact, ELBMF and PRIMP perform similarly across board is highly encouraging, unlike PRIMP, ELBMF does not require post-processing. For Asso and GRECOND, recall and similarity drop considerably, but they exhibit a slightly higher recall". This means that these methods are robust against noise, but they fail to recover the remaining information. Starting low, ORM's 's recalls increase jointly with the noise level, suggesting that clean data is problematic for ORM. Reporting the standard deviations as the shaded region, variance across all similarities except for Asso and NMF the highest noise regime. The deviation of both recalls is, however, inconsistent for most methods, except for BINAPS, PRIMP, and ELBMF. Overall, the performance characteristics of ELBMF are among the most reliable.
little
How robust is ELBMF regarding varying matrix densities? To understand whether ELBMF performs consistently well on low- high-density matrices, we generate synthetic matrices before, this time using fixed noise of 0.2, and varying the width and height the ground-truth squared tiles from 32 12a resulting in densities between 0.0375 to 0.6, before noise.
In Fig. 4, we show the similarity, recall, and loss of BINAPS, AssO, GRECOND, ORM, SOFA, NMF, PRIMP, and ELBMF. We can see that the increasing density affects the performance of all
7

---

9.95
10
10.4
9.9
8.4 10*
10.3
Bai & Ng
AIC
MDL
8.2 10*
10.2
9.85
8 10"
10.1
7.8 104
10
0.75
7.6 10*
9.9
07
17
10
30
10
20
30
10
20
30
Rank
Figure 5: Using AIC, MDL, or Bai & Ng's first information criteria, ELBMF correctly detects the simulated 400 300 matrix of rank 10 which we applied 10% additive noise.
methods, however, does not affect the performance all methods equally. All methods-exeee ORM-improve in similarity, recall, and loss. With increasing density, ORM gets worse at first, before its loss shrinks significantly, such that it finishes outperforming SOFA and BINAPS. From low to high density, ELBMF is the best best-perforning method across the board in similarity, recall, and loss.
Does ELBMF estimate the underlying Boolean matrix rank correctly? When a target rank is known, we can immediately apply ELBMF to factorize the data. In the real world, however, the target rank might be unknown. this case, we need to estimate an appropriate choice from the data, and we use synthetic data to ensure that ELBMF does correctly.
Since a higher matrix rank usually also means a better fit, selecting the best rank according to recall, loss, or similarity leads to overfitting peefftting-uuless unless we properly account for the growth in model complexity. There are many model selection criteria that penalize complex models, such as AIC [1], Bai & Ng's criteria [4, 2]. Nuclcar- norm regularizing [20, 12]. the information cormattioo--hoorttii Minimal Description Length principle (MDL) [11], or (Decomposed) Normalized Maximum Likelihood [19, 41]. Follow- ing common practice, and motivated by its practical performance in preliminary experiments, we [X]
choose MDL. That is, select the minimizer of the of the log binomial ((X) log (1xx of the error matrix and the rows and columns of factorization (assumed be i...d) [26]
I(A @ o V]) + ΣiEW I(UT) I(V,) log(n -m).
To validate whether ELBMF recovers the correct rank, we synthetically generate a 400 300 matrix of ground-truth rank 10 with 10% additive noise. In Fig. show AIC, MDL, and Bai & Ng's first criterion for each rank up to 30, finding that our method precisely discovers the right rank.
4.2 Performance ELBMF on Real-World Data
Having ascertained that ELBMF works well on synthetic data, we turn to its performance in the real world. Here, we use nine publicly available datasets from different domains. To cover the biomedical domain, we extract the network containing empirical evidence of protein-protein interactions in Homo sapiens from the STRING database. From the GRAND repository, we take the gene regulatory networks sampled from Glioblastoma (GBM) and Lower Grude Glioma (LGG) brain cancer tissues, well as from non-cancerous Cerebellum tissue. The TCGA dataset contains binarized gene expressions from cancer patients, and we further obtain the single nucleotide polymorphism (SNP) mutation data from the Genomes project, following processing steps from the authors of BINAPS [9]. In the entertainment domain, use the user-movie datasets Movielens and Netflix, binarizing the original 5-star-scale ratings by setting only reviews with more than 3.5 stars to 1. Finally, as data from the innovation domain, derive directed citation network between patent groups from patent citation and classification data provided by Patents View. For each dataset with a given number of groups, such cancer types or movie genres, set the matrix rank l: 33 (TCGA), 28 (Genomes). 136 (Patents), 20 (Movielens), and 20 (Netflix). When the number of subgroups is unknown, we estimate the rank that minimizes MDL using ELBMF, resulting in 100 (GBM), 32 (LGG), 100 (String), and 450 (Cerebellum).
2 GRAND NETWORKMEDICINE, ORG STRING-DB.ORG CANCER GOV/TCGA INTERNATIONALCENOMEE PATENTS IITENTSVIEW.OR GROUPLENS.CO ORC//DATASETS//MOVIELSSS KACGLE. AAGLLLL.CODDDAASRRRTSEEEELLILSS

---

Netflx
Movieleus
ASSO
Patents
Oa Lif
GRECOND
String
10
On
O ORM
Cerebellum
9.6
0
SOFA
BINAPS
GBM
NMF
TCGA
Genomes
A.
0.2 0.4 0.6
0.8
0.2 0.4 0.6
0.8
0
0.2 0.4
0.6 0.8
110" 10 102
10
O ELBMF
(a) Relative Loss
(b) Similarity
(c) Recall
(d) Time [s]
Figure Our method factorizes real-world data with high similarity and recall, as well low relative loss and runtime. We report relative loss, similarity, recall, and runtime of 9 real-world matrices and their reconstructions from Asso, GRECOND, ORM, SOFA, BINAPS, NMF, PRIMP, and ELBMF.
As we can achieve high similarity with an all-zeros reconstruction (in the case of sparse data), or a perfect recall with an all-ones reconstruction, we also report the relative loss (lower is better),
A ||A Uo VIII
between the target matrices and their reconstructions.
We show relative loss, similarity, recall, and runtime of Asso, GRECOND, SOFA, ORM, BINAPS, NMF, PRIMP, and ELBMF, applied to all real-world datasets, targeting a given matrix rank, in Fig. 6. The cover-based GRECOND and Asso show comparable loss, similarity, and recall. Both perform better smaller matrices (LGG, GBM, or Cerebellum) and struggle with complex matrices (e.g., TCGA, Genomes). On the complex matrices (c.g., on TCGA, String, or Movielens), although always outperformed by ELBMF, we see that the rounded NMF reconstructions are surprisingly good, occasionally surpassing dedicated BMF methods, such as Asso, GRECOND, ORM, and SOFA. Across the board, GRECOND, Asso, ORM, SOFA, BINAPS, and NMF almost always result in considerably higher loss than ELBMF. Compared to the close competitor PRIMP, our method ELBMF always results in lower reconstruction loss. We observe the largest gap between the two on the Cerebellum dataset, where PRIMP'S s grid search procedure fails to find suitable thresholds. This is an impressive result because unlike PRIMP, ELBMF does not necessitate heavy post-processing.
In Fig. 6b, we see that all methods except BINAPS result in a high similarity, which implies they are sparsity-inducing. As BINAPS overfits and densely reconstructs sparse inputs, it surpasses sparsity- inducing methods in recall. Considering non-overfitting methods, however, ELBMF is among the best performing terms or recall, often outperforming PRIMP, while under significantly stronger regularization. When PRIMP has a higher recall (c.g., Genomes), this often comes with a higher loss GRECOND, ORM,
than ELBMF. We see in Fig. 6d (log scale) that that-except for few SOFA, and PRIMP are slower than ELBMF. Although NMF is less constrained than ELBMF, both are almost on par when it comes to runtime. Degraded by post-processing, our closed competitor PRIMP is almost always much slower than ELBMF and struggles with Netflix. Only BINAPS and ELBMF finished Netflix, however, only ELBMF did so reasonable loss, considering the given target rank.
4.3 Exploratory Analysis of Gene Expression Data with ELBMF
Knowing that ELBMF performs well quantitatively, we ask whether its outputs are also interpretable. To this end, we take closer look at the TCGA data, which contains the expression levels of 20 530 genes from 10 459 patients, who are labeled with 33 cancer types. Since we are interested in retaining high gene expression levels only, we expression levels to one if their z-scores fall into the top 5% quantile, and to zero otherwise [23]. We run ELBMF on this dataset, targeting a rank of 33.
To learn whether our method groups patients meaningfully, we visualize the target matrix and its reconstruction. As the target matrix is high- dimensional. we embed both the target matrix and the reconstruction into a two-dimensional space using t-SNE [39] as illustrated in Fig. 7, where each color corresponds to one cancer type. In Fig. 7a, we show that when embedding the target matrix directly, the cancer types are highly overlapping and hard to distinguish without the color coding. In contrast, when embedding our reconstruction, depicted in Fig. 7b, we see clean segmentation into clusters that predominantly contain single cancer type.

---

NM1
Type
0.8
1:SNN
C-NN 2
0.6
17
0.4
0.2
26
0.0
-5
33
-5
5
-5
0
(-SNE
I-SNE
Index of Estimated Component
(a) TCGA
(h) Reconstructed TCGA
(c) Normalized Mutual Information
Figure 7: ELBMF discovers the hidden structure gene expression data. We show the two- dimensional t-SNE embedding of the TCGA dataset (a) and the embedding of its reconstruction from ELBMF (b), where each point corresponds to one of the 10 459 patients, colored by cancer type. While the cancer types are hard to differentiate in the embedding of the original dataset (a), they separated into easily distinguishable clusters in the embedding of our reconstruction (b). In (c), we show the normalized mutual information between estimated groups and cancer types, and observe that there is an almost 1-to-1 correspondence between our estimated groups and the cancer types.
To better understand these results, we quantify the association between our 33 estimated components and the ground-truth cancer types by computing the normalized mutual information matrix. This matrix is noticeably sparse (Fig. 7c), leading to clean segmentation. Upon closer inspection with discover turn out to be biologically meaningful. For example, find that ELBMF associates a set of 356 genes to patients with thyroid carcinoma. This component is associated with thyroid hormone generation and thyroid gland development, and statistically significantly so-even under a strict False Discovery Control, with p-values as low as 2.574 x 10-8 and 6.530 x 10-6
ENRICHR [8], the associations
5 Conclusion
We introduced ELBMF to efficiently factorize Boolean matrices using an elegant and simple algorithm that, unlike its closest competitors, does not rely on heavy post-processing. ELBMF considers a novel relaxed BMF problem, which allows intermediate solutions to be real-valued. It solves this problem by leveraging an efficiently computable proximal operator, derived from the innovative ELB regularizer, and using a regularization rate to obtain Boolean factors upon convergence. Experimentally, we have shown that ELBMF works well in practice. It operates reliably on synthetic data, outperforms the discrete state of the art, is at least good as the best relaxations on real data, and yields interpretable results even difficult wittins-without relying on post-processing.
Limitations Although ELBMF works overall, it has two bottlenecks. First, by randomly initializing factors, we start with highly dense matrices, thus prohibiting efficient sparse matrix operations. This is not ideal for sparse datasets that are too large to fit into memory, and future research on sparse initialization of Boolean factors will benefit not only ELBMF but also many other methods. Second, the larger the datasets, the higher the cost of computing gradients, and future work might adapt stochastic gradient methods for ELBMF mitigate this problem.
Broader Impact ELBMF is a method for factorizing Boolean matrices, which permits interpretable, rather than black-box data analysis. As such, it can help make explicit any biases that may be present in the data. Just like any other method for interpretable data analysis, the insights ELBMF yields can be used for good purposes (c.g., insight into cancer-causing mutations) or for bad purposes, and the ultimate quality of the outcome also depends on the behavior of the user. In our experiments, we focus on beneficial applications, and only consider anonymized open data.
10

---

References
[1] H. Akaike. new look at the statistical model identification. JEEE Transactions on Automatic Control, 19(6):716-723, 12 1974.
[2] Lucia Alessi, Matteo Barigozzi, and Marco Capasso. Improved penalization for determining the number of factors in approximate factor models. Statistics Probability Letters, 80(2-
2010.
[3] Miguel Araujo, Pedro Manuel Pinto Ribeiro, and Christos Faloutsos. Faststep: Scalable boolean matrix decomposition. In Advances in Knowledge Discovery and Data Mining 20th Pacific- Asia Conference, PAKDD 2016, Auckland, New Zealand, April 19-22, 2016, Proceedings, Part I, volume 9651 of Lecture Notes in Computer Science, pages 461 461-473. Springer, 2016.
[4] Jushan Bai and Serena Ng. Determining the number of factors in approximate factor models. Econometrica, 70(1):191-2211 2002.
[5] Radim Belohlávek and Martin Tmecka. A new algorithm for boolean matrix factorization which admits overcovering. Discret. Appl. Math. 249:36-52 52, 2018.
[6] Radim Belohlávek and Vilém Vychodil. Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Comput. Syst. Sci., 76(1):3 (6(1))33200) 20, 2010.
[7] Jérôme Bolte, Shoham Sabach, and Mare Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program., 146(1-2) 4944 2014.
[8] Edward Y. Chen, Christopher M. Tan, Yan Kou, Qiaonan Duan, Zichen Wang, Gabriela Vaz Meirelles, Neil R. Clark, and Avi Ma' ayan. Enrichr: interactive and collaborative HTML5 gene list enrichment analysis tool. BMC Bioinform. 14:128, 2013.
[9] Jonas Fischer and Jilles Vreeken. Differentiable pattern set mining. In KDD '11: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 383-392. ACM, 2021.
[10) Gene H. Golub and Charles F. Van Loan. Matrix Computations, Third Edition. Johns Hopkins University Press, 1996.
[11] Peter D. Grünwald. The Minimum Description Length Principle. The MIT Press, 2007.
[12] Suriya Gunasekar, Blake F. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017,
December 4-9, 2017, Long Beach, CA, USA, pages 6151-6159, 2017.
[13] Ali Haddad, Foroogh Shamsi, Li Zhu, and Laleh Najafizadeh. Identifying dynamics brain function via boolean matrix factorization. In 52nd Asilomar Conference on Signals, Systems, and Computers, ACSSC 2018, Pacific Grove, CA, USA, October 28-31, 2018, pages 661-665. IEEE, 2018
[14] Sibylle Hess and Katharina Morik. C-SALT: mining class-specific alterations in boolean matrix factorization. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18-22. 2017, Proceedings, Part I, volume 10534 of Lecture Notes in Computer Science, pages 547-563. Springer, 2017.
[15] Sibylle Hess, Katharina Morik, and Nico Piatkowski. The PRIMPING routine tiling through proximal alternating linearized minimization. Data Min. Knowl. Discov,, 31(():1090 1131, 2017.
[16] Sibylle Hess, Nico Piatkowski, and Katharina Morik. The trustworthy pal: Controlling the false discovery rate in boolean matrix factorization. In Proceedings of the 2018 SIAM International Conference on Data Mining, SDM 2018, May 3-5, 2018, San Diego Marriott Mission Valley, San Diego, CA. USA, pages 405-413. SIAM, 2018.

---

[17] Sibylle Hess, Gianvito Pio. Michiel E. Hochstenbach, and Michelangelo Ceci. BROCCOLI: overlapping and outlier-robust biclustering through proximal stochastic gradient descent. Data Min. Knowl. Discov, 35(6):55422255757 2576, 2021.
[18) Dmitry I. Ignatov, Elena Nenova, Natalia Konstantinova, and Andrey V. Konstantinov. Boolean matrix factorisation for collaborative filtering: An fea-based approach. In Artificial Intelligence: Methodology; Systems, and Applications 16th International Conference, AIMSA 2014, Varna, Bulgaria, September 11-13, 2014. Proceedings, volume 8722 of Lecture Notes in Computer Science, pages 47-58. Springer, 2014.
[19] Yu Ito, Shinichi Oeda, and Kenji Yamanishi. Rank selection for non-negative matrix factorization with normalized maximum likelihood coding, In Proceedings of the 2016 SIAM International Conference on Data Mining, Miami, Florida, USA, May 5-7, 2016, pages 720-728. SIAM, 2016.
[20] Martin Jaggi and Marek Sulovský. A simple algorithm for nuclear norm regularized problems. In Proceedings of the 27th International Conference Machine Learning (ICMI-10), June 21-24, 2010, Haifa, Israel, pages 47 1-18. Omnipress. 2010.
[21] Daniel
Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788-99. October 1999. Number: 6755 Publisher: Nature Publishing Group.
[22] Daniel D. Lee and H. Sebastian Scung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA, pages 556-562. MIT Press, 2000.
[23] Lifan Liang, Kunju Zhu, and Songjian Lu. BEM: mining coregulation patterns in transcriptomics via boolean matrix factorization. Bioinform., 36(13):403--4337, 2020.
[24] Pauli Miettinen, Taneli Mielikäinen, Aristides Gionis, Gautam Das, and Heikki Mannila. The discrete basis problem. IEEE Trans. Knowl. Data Eng., 200100:134888110 1362, 2008
[25] Pauli Miettinen and Stefan Neumann. Recent developments boolean matrix factorization. In Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pages 4922-4925 ijcai.org, 2020.
[26] Pauli Miettinen and Jilles Vreeken. MDL4BMF: minimum description length for boolean matrix factorization. ACM Trans. Knowl. Discov. Data, 8(4):18:1-18:31, 2014.
[27] Sylvia D Monson, Norman Pullman, and Rolf Rees. A survey of clique and biclique coverings and factorizations of (0, -mmatricss. Bull. Inst. Combin. Appl, 14:17-86, 1995.
[28] Stefan Neumann. Bipartite stochastic block models with tiny clusters. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3871-3881, 2018.
[29] Stefan Neumann and Pauli Miettinen. Biclustering and boolean matrix factorization in data streams. Proc. VLDB Endow, 13090):1709-1722 2020.
[30] James Orlin. Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 8065):00--424, 1977.
[31] Pentti Paatero and Unto Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, (22):11-1222 1994.
[32] Neal Parikh and Stephen P. Boyd, Proximal algorithms. Found. Trendy Optim., 1(3):127-339 2014.
[33] Thomas Pock and Shoham Sabach. Inertial proximal alternating linearized minimization (ipalm) for nonconvex and nonsmooth problems. SIAM J. Imaging Sci., 174): 2016.
12

---

[34] Siamak Ravanbakhsh, Barnabás Póczos, and Russell Greiner. Boolean matrix factorization and noisy completion via message passing. Proceedings of the 33nd International Conference on Machine Learning, ICML. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 945-954, JMLR.oo.. 2016.
[35] Tammo Rukat, Christopher C. Holmes, Michalis K. Titsias, and Christopher Yau. Bayesian boolean matrix factorisation. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 Proceedings of Machine Learning Research, pages 2669-997... PMLR, 2017.
[36] Tammo Rukat, Christopher C. Holmes, and Christopher Yau. Probabilistic boolean tensor de- composition. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssunn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 4410-4419, PMLR, 2018.
[37] Tammo Rukat, Dustin Lange, and Cedric Archambeau. An interpretable latent variable model for attribute applicability the amazon catalogue. In NeurIPS 2017, 2017.
[38] Nikolaj Tatti and Pauli Miettinen. Boolean matrix factorization meets consecutive ones property. In Proceedings of the 2019 SIAM International Conference Data Mining, SDM 2019, Calgary, Alberta, Canada, May 2-4, 2019, pages 729-737. SIAM, 2019.
[39] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11)) 2008.
[40] Changlin Wan, Wennan Chang, Tong Zhao, Mengya Li, Sha Cao, and Chi Zhang. Fast and efficient boolean matrix factorization by geometric segmentation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 6086-6099 AAAI Press, 2020.
[41] Tianyi Wu, Shinya Sugawara, and Kenji Yamanishi. Decomposed normalized maximum likelihood codelength criterion for selecting hierarchical latent variable models. Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 17, 2017, pages 1165-1174. ACM, 2017.
[42] Zhongyuan Zhang, Tao Li, Chris H. Q. Ding, and Xiang -Sun Zhang. Binary matrix factorization with applications. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007), October 28-31, 2007, Omaha, Nebraska, USA, pages 391-400. IEEE Computer Society, 2007.
[43] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301-320, 4 2005.
13


Reviews:
[{"review_id": "l5aIeS1tCVc", "reviewer": "Reviewer_t3GQ", "summary": "This paper relaxed Boolean matrix factorization under linear algebra. They proposed a novel elastic BMF regularizer to ensure Boolean factors for the decomposition. They also showed useful applications of the proposed methods in the analysis of biological data. ", "questions": "As in weaknesses, my main concerns as the advantage of relaxing compared with traditional BMF and the experimental setting.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed elastic BMF regularizer that penalize the value distribution to ensure the Boolean factors. \n2. The proposed method showed empirical better performance with some classic BMF methods.\n3. They also showed promising applications across different domains.\n\nWeaknesses:\n1. Binary matrix can easily be high rank under linear algebra, thus prevent the application of many classic methods like SVD. While under Boolean algebra, optimally, the rank of the matrix can be reduced to its log level. As far as I regard, this is the main advantage to apply BMF in analyzing binary data. By relaxing the problem to NMF under linear algebra while ensuring Boolean factors does not solve the high rank issue of binary matrix. It thus posed a question of how practical this proposed method is useful in analyzing binary data. \n2. The experimental design is not quite fair. The data is synthesized with rectangular non-overlapping tiles, which is quite rear for binary data, where overlapping is very common.\n3. I am also confused that in figure 2b, why the error converged not on the smallest error. Is it because the penalization of Boolean factors cost extra error in the factorization? If so, how to quantify such tradeoff?\n4. The author discussed lots of related methods but only compared with very few of them. Like the most recently probabilistic methods from Ravanbakhsh et al, Rukat et al. As for the relaxing method, I also notice a rather recent method called Faststep: Scalable boolean matrix decomposition. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "eRzmmAjzkJi", "reviewer": "Reviewer_fNGy", "summary": "The authors propose a continuous relaxation to Boolean matrix factorisation that makes the problem amenable to gradient descent. A regularizer term mediates the relaxation and is consecutively reduced to obtain a Boolean solution. The method is shown to perform well on synthetic data and on-par or favorable compared to alternative methods on real-world data. The authors demonstrate that it infers semantically meaningful factors on a genomic example.", "questions": "- l. 6 \"efficient\" is meaningless without metric or comparison. Same in l 43., \"elegant, accurate and efficient\" without context are void terms.\n\n- l. 24, the authors claim that methods like PCA are not interpretable for Boolean data because they have a different domain. I don't think this reasoning is self-evident. E.g., if one uses PCA with a link function with binary output, the results should be interpretable in some ways. Maybe the reasoning here could be a bit more specific?\n\n- l. 56-58: Unnecessary jargon. BMF can be introduced in much simpler terms.\n\n- Instead of MDL, can you assess the generalization performance on held-out data (heldout matrix entries)?", "limitations": "Properly addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Well and clearly written, easy to follow. Thank you!\n\n- From the empirical results (especially Fig. 5) the claim that the method is improves over SOTA is not clearly warranted. I think this is a major limitation.\n\n- Some competitors are missing from the comparison. E.g., why no comparison with Rukat et al? (Probabilistic sampling approach - https://proceedings.mlr.press/v70/rukat17a.html).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-gnykDZFr9V", "reviewer": "Reviewer_Bmfn", "summary": "The authors propose an elastic net inspired approach for the optimization of Boolean Matrix Factorizations (BMF). Relying on a relaxed objective with regularization towards binary values, they derive the proximal operator for the proposed regularization, enabling the use of Proximal Alternating Minimization. A gradual increase of the regularizer weights is supposed to alleviate the problem of being trapped in local minimizers. The experimental analysis shows that the proposed method maintains desirable properties, such as robustness to noise and feasibility to determine the rank of the factorization, while being less computationally expensive.", "questions": "* How does the gradual increase of the regularization weights work? Do you not optimize the binary MF objective with this approach? \n* How much overlap between clusters (tiles) is in the synthetic data?\n\n# After Rebuttal Thoughts\nAs I laid out in my author's response, I think that there is an obvious contribution of the proposed elastic net binary penalizer. I also think that the optimization with a gradual increase of the penalization weights leads to a good optimization scheme that is less likely to be stuck in unsuitable local minimizers. I think that the framing of the proposed method is maybe not optimal, but it's not exactly wrong. Because I think that the authors will be able to improve the framing and because I see the contribution of the paper, I increase my score to accept. ", "limitations": "There is no designated Limitations section but a broader impact section, describing potential ethical aspects. I think this should be clear, that methods as the proposed one can be possibly misused. If it were according to me, I would say the authors can scrap this section and instead explain the method a bit more in detail. \nApart from the mentioned question about binary vs. Boolean factorizations, I don't see any limitations that should be discussed here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* The paper is well-written and good to follow (by and large)\n* The proposed approach is extremely sound (except for one thing mentioned below). Applying best practices from L1- and L2- regularization to the L1- and L2- inspired binary regularization terms makes a lot of sense. I also expect that the gradual increase of the weights helps to obtain better minimizers (although this doesn't show that much in the experiments)\n* The experimental analysis is well done, addressing many relevant aspects of BMF (determination of the rank, robustness, synthetic and real-world data)\n\n# Weaknesses\n* I take from the paper that the matrices are optimized by PALM until they are binary. This is weird because that would mean that the factorization is computed in elementary algebra. A strongly  regularized elastic BMF is equivalent to solving the objective of binary matrix factorization:\n $$\\min \\lVert A-UV\\rVert^2 \\text{ s.t. }U\\in\\\\{0,1\\\\}^{n\\times k}, V\\in\\\\{0,1\\\\}^{k\\times m}$$\nHowever, that is not the objective of Boolean factorization, where the matrix product is computed in Boolean algebra. That is why Primp relies on a post-processing step: a relaxed, almost binary result can mock the properties of the BMF after rounding. \n\nI would be happy to accept this paper, but the issue above should be clarified before I can vote for acceptance. \n\n# Minor Issues/Comments\n* What is the definition of $\\oplus$ in Eq. (2)?\n* How the gradual increase of the regularization weights is performed, is a bit unclear. The text states that in every iteration the weight is increased by multiplication with $\\nu_t$. However, I didn't see in the experiments section how $\\nu_t$ is determined.\n* The MDL choice is not very well motivated. I see that there might be space restrictions, but maybe this could be a bit more explained.\n* Some of the terminologies are not really introduced, like tiles.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept