Likelihood-based weighting sharpens boolean matrix factorization and correlation clustering

Their new study, published in Data Mining and Knowledge Discovery, proposes a principled way to choose these weights by maximizing the likelihood of a simple statistical model, and shows that the resulting search comes with provable approximation guarantees while remaining practical enough to run on real benchmark datasets. The two problems in question are boolean matrix factorization and correlation clustering. Boolean matrix factorization summarizes a binary matrix by finding a small number of tiles, dense blocks of ones, that together reconstruct the input as faithfully as possible.

Correlation clustering, by contrast, takes a graph whose edges are labeled positive or negative and partitions the vertices so that negative edges inside clusters and positive edges between clusters are minimized. Although these tasks look different on the surface, the authors observe that both can be cast as the same abstract problem: given a binary vector and a restricted set of candidate vectors, find the candidate that minimizes a weighted count of disagreements with the input. The trouble with minimizing disagreements is that the standard, unweighted version behaves badly on sparse data.

In the matrix case, the disagreement count can be rewritten as a constant minus the number of ones covered by the tiles plus the number of zeros covered. A tile is therefore only worth adding if it covers more ones than zeros, which effectively demands that every accepted tile have density at least one half. Real datasets are often extremely sparse, so genuinely interesting structure can be far less dense than that threshold, and the criterion ends up favoring only tiny, very dense fragments while ignoring broader, weaker patterns.

A natural fix is to weight the two kinds of disagreement differently, penalizing missed ones and falsely covered zeros by separate factors. This idea has been used before, but it introduces a new headache: nobody tells you what the weights should be. The choice matters enormously.

Push the weight of ones too high and the algorithm will cover every single one in the data, smothering the summary in noise; push it too low and the tiling refuses to include any zeros at all, shrinking to trivially safe tiles. The same dilemma appears in correlation clustering, where an imbalance between positive and negative edges can shatter the graph into a flood of tiny clusters unless the disagreements are rebalanced. Tatti and Adriaens' key insight is to stop treating the weight as a free parameter and instead derive it from a statistical model.

They model each entry of the input with two Bernoulli variables: one governs the probability of seeing a one in positions that the candidate summary marks as one, and the other governs positions marked as zero. The goal then becomes maximizing the likelihood of the observed data under this two-parameter model. Crucially, the authors prove that for any such model there exists an equivalent weight for the disagreement objective, so the likelihood-optimal summary is also optimal for a suitably weighted disagreement problem.

The statistical criterion thus becomes a principled weight selector. Finding the optimal likelihood directly would require enumerating an impractical number of parameter combinations, so the authors design efficient search procedures. Their first algorithm, called SGrid, searches over the weight parameter on a geometric grid, multiplying the current weight by a factor of one plus epsilon at each step.

The authors prove that this multiplicative stepping preserves quality: if the underlying weighted problem can be solved with an alpha-approximation guarantee, SGrid returns a solution within a factor of alpha times one plus epsilon of the likelihood optimum, using only a logarithmic number of queries in the input size. For correlation clustering on general graphs, plugging in known algorithms yields roughly a logarithmic approximation guarantee, and on complete graphs a constant factor of three times one plus epsilon is achievable under suitable assumptions. The second algorithm, Pruned, exploits a fractional-programming technique to cut the number of solver calls dramatically in practice.

After solving the weighted problem for a candidate weight, the algorithm computes the implied model parameters and derives the weight that would make that solution self-consistent. The authors prove that this implied weight is a monotonically increasing function of the queried weight, which allows the search to skip entire intervals that cannot contain the optimum. When the underlying solver is exact, Pruned retains the same one-plus-epsilon approximation guarantee as SGrid, but experiments show it slashes the query count at tight tolerance levels: at epsilon equal to 0.01, boolean matrix factorization queries dropped from 577 to 34, and correlation clustering queries from 567 to 68, compared with the plain grid search.

Beyond the algorithms themselves, the paper contributes theoretical reassurance that the likelihood objective is meaningful in the long run. For boolean matrix factorization, the authors show that when data are generated by independently sampling each cell from a probability matrix, and the true factorization is unique, the likelihood-optimal factorization of a large enough sample converges to the factorization that minimizes the expected cost, meaning sampling noise washes out as the data grow. An analogous concentration result holds for correlation clustering under a stochastic block model: if the planted community structure uniquely minimizes the expected cost, the likelihood-optimal clustering recovers it with high probability as the number of nodes increases.

The uniqueness conditions are not decorative; the authors exhibit counterexamples where non-unique factorizations cause the guarantee to fail. The empirical evaluation spans synthetic and real data. On synthetic matrices built from intersecting tiles with varying interior density, the likelihood-driven search recovered ground-truth tiles far better than the classical Asso algorithm, which uses unweighted disagreements and consequently misses rows and columns inside sparser tiles.

On graphs from a stochastic block model, the new approach resisted the proliferation of tiny clusters that plagued the unweighted baseline as cluster density dropped. The authors are candid about the model's limits: because it uses only two parameters, one for all tiles and one for the background, it can miss sparse clusters whose density sits closer to the background noise level than to the shared tile density, and a more flexible baseline with per-tile parameters won on datasets with strongly heterogeneous tile densities. On real benchmarks, including paleontological fossil records, DNA copy-number amplification data, mammal distribution atlases, and standard market-basket datasets, the grid-search methods achieved better likelihood scores than all tested baselines and often produced larger, sparser tiles that captured more of the data's ones, as illustrated by a decomposition of the paleontology dataset that Asso fragmented into small, very dense pieces.

The authors note that exact solution of either problem is computationally infeasible in general, so their experiments relied on heuristic solvers, and they flag the development of faster algorithms that optimize weights and solutions simultaneously as a promising direction. For now, the work offers data miners something they have long lacked: a defensible, automatic answer to the question of how much each mistake should cost.

Subject of Research: A likelihood-based method for selecting disagreement weights in boolean matrix factorization and correlation clustering

Article Title: Weighting disagreements with likelihood for boolean matrix factorization and correlation clustering

Article References: Tatti, N., & Adriaens, F. (2026). Weighting disagreements with likelihood for boolean matrix factorization and correlation clustering. Data Mining and Knowledge Discovery, 40(6), Article 118. https://doi.org/10.1007/s10618-026-01278-9

Image Credits: AI Generated

DOI: 10.1007/s10618-026-01278-9

Keywords: boolean matrix factorization, correlation clustering, likelihood, grid search, approximation algorithms, data mining, stochastic block model, Bernoulli model, weighted disagreements, fractional programming, tile mining, graph partitioning