Weighting disagreements with likelihood for boolean matrix factorization and correlation clustering

Abstract Boolean matrix factorization is a popular technique for summarizing a binary matrix. The goal in such summary is to find k tiles that are denser than the rest of the data: a typical objective is to minimize the number of (weighted) disagreements with the input data. Another instance of minimizing weighted disagreements is correlation clustering, where we are given a graph with signed edges and are asked to partition a graph minimizing the negative intra edges and the positive inter edges. We argue that weighting disagreements in both cases is crucial, especially for sparse datasets. This leads to a problem of selecting an appropriate weight: a non-trivial problem as we cannot use the original objective directly. To solve this issue we propose an alternative strategy: we search for results that maximize the likelihood of a simple model, based on two Bernoulli variables. We then show that we can find good solutions using a grid search. We develop 2 grid search strategies. The first approach requires $$\mathcal {O}\left( (1 + \epsilon ^{-1}) \log \ell \right)$$ queries, where $$\ell$$ is the size of the input, and yields $$(1 + \epsilon )\alpha$$ guarantee if we can $$\alpha$$ -approximate the original weighted disagreement problem. The second approach is a pruning technique, based on fractional programming, that reduces the number of queries significantly in practice, especially for small $$\epsilon$$ . This approach yields $$(1 + \epsilon )$$ approximation guarantees, if we can solve the original weighted disagreement problem exactly. We demonstrate empirically that weighting disagreements produces more accurate results, and study the cases where the grid search yields better likelihood scores than the selected baselines.