Introduction
Standard clustering techniques typically focus on grouping data points along a single dimension—for instance, grouping users by their movie preferences. However, many modern data analysis tasks require simultaneous partitioning of both dimensions of a data matrix. This problem, known as co-clustering (or biclustering), aims to find a grid-like structure of "blocks" or "submatrices" where values within each block are close to their local average. Co-clustering is essential in fields such as text mining, bioinformatics, and recommendation systems.
Despite its utility, co-clustering is computationally significantly more challenging than one-sided clustering. Historically, researchers have relied on heuristics that, while effective in practice, lacked theoretical guarantees. This paper presents the first constant-factor approximation algorithms for the co-clustering problem across a wide range of matrix norms.
The Co-clustering Problem
The objective of co-clustering is to partition the $m$ rows and $n$ columns of a matrix $A$ into $k$ row clusters and $\ell$ column clusters, respectively. This results in a $k \times \ell$ grid of blocks. The quality of the co-clustering is measured by how well the original matrix can be approximated by a block-constant matrix.
The authors prove that $(k, n^\epsilon)$-co-clustering is NP-hard for $\ell_1$ and $\ell_2$ norms, justifying the search for approximation algorithms rather than exact solutions.
Methodology: Independent Decomposition
The central innovation of this work is a remarkably simple strategy: decomposing the intertwined row-column problem into two independent one-sided clustering problems.
1. Independent One-Sided Clustering
The first step involves treating the rows as points in space and finding an $\alpha$-approximate clustering. This is equivalent to solving a one-sided clustering problem where the goal is to minimize the distance between rows and their respective cluster centroids.
To achieve this, the authors solve a sub-problem termed $k$-means$_p$, a generalization of $k$-means for $\ell_p$ norms. They provide a 16-approximation algorithm for this problem for any $p \ge 1$.
2. Independent Column Clustering
The same process is applied to the columns of the matrix, treating them as points and finding an $\alpha$-approximate partitioning into $\ell$ clusters.
3. Combination
The final co-clusters are defined by the intersection of these independent row and column partitions. The value assigned to each block is the mean of the original matrix entries within that block.
Theoretical Guarantees
The authors provide a rigorous proof that this decoupled approach yields a $3\alpha$-approximation for general $\ell_p$ norms. This means the resulting solution is guaranteed to be within a factor of $3\alpha$ of the global optimum.
For the specific case of the Frobenius norm ($p=2$), the authors leverage the geometric properties of Hilbert spaces to tighten this bound to $\sqrt{2}\alpha$. Furthermore, when the number of clusters $k$ and $\ell$ are fixed constants, they demonstrate a $(\sqrt{2} + \epsilon)$-approximation.
Key Insights
- The Power of Decomposition: The "intertwined" nature of co-clustering does not necessitate a simultaneous optimization approach to achieve a constant-factor guarantee. You don't lose much by ignoring the column structure while clustering rows, and vice versa.
- Residue Sensitivity: The guarantees apply to "mean-based" residues. More complex objectives, such as those accounting for simultaneous row and column biases (e.g., the Cheng-Church algorithm), remain an open challenge for approximation.
- Exact Solutions for Special Cases: The paper shows that $(k, 1)$-co-clustering (clustering rows while keeping all columns in one group) can be solved exactly in $O(mn + m^2k)$ time for the Frobenius norm using dynamic programming.
Conclusion and Future Work
This work moves co-clustering from a heuristic-driven field to one with solid theoretical foundations. Future research directions include extending these approximation techniques to broader classes of distance measures, such as Bregman divergences (including KL-divergence), and addressing more complex residue definitions used in specific domains like bioinformatics.
Summary updated