Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: # Strengths
* The paper is well-written and good to follow (by and large)
* 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)
* The experimental analysis is well done, addressing many relevant aspects of BMF (determination of the rank, robustness, synthetic and real-world data)

# Weaknesses
* 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:
 $$\min \lVert A-UV\rVert^2 \text{ s.t. }U\in\\{0,1\\}^{n\times k}, V\in\\{0,1\\}^{k\times m}$$
However, 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. 

I would be happy to accept this paper, but the issue above should be clarified before I can vote for acceptance. 

# Minor Issues/Comments
* What is the definition of $\oplus$ in Eq. (2)?
* 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.
* 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.
* Some of the terminologies are not really introduced, like tiles.
questions: * How does the gradual increase of the regularization weights work? Do you not optimize the binary MF objective with this approach? 
* How much overlap between clusters (tiles) is in the synthetic data?

# After Rebuttal Thoughts
As 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. 
Apart from the mentioned question about binary vs. Boolean factorizations, I don't see any limitations that should be discussed here.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strengths:
1. The proposed elastic BMF regularizer that penalize the value distribution to ensure the Boolean factors. 
2. The proposed method showed empirical better performance with some classic BMF methods.
3. They also showed promising applications across different domains.

Weaknesses:
1. 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. 
2. 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.
3. 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?
4. 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. 
questions: As in weaknesses, my main concerns as the advantage of relaxing compared with traditional BMF and the experimental setting.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: - Well and clearly written, easy to follow. Thank you!

- 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.

- 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).

questions: - l. 6 "efficient" is meaningless without metric or comparison. Same in l 43., "elegant, accurate and efficient" without context are void terms.

- 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?

- l. 56-58: Unnecessary jargon. BMF can be introduced in much simpler terms.

- Instead of MDL, can you assess the generalization performance on held-out data (heldout matrix entries)?
limitations: Properly addressed.
review_title: null

Meta-review: metareview: This was a border-line paper, but I recommended accepting it , mainly due to the impressive rebuttal that answered at least most of my concerns.
There were issues with the experimental results, but I believe most of them can be fixed since the authors provided full source code (which is not so common).


confidence: Less certain
Decision: Accept