Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs

Jiaming Xu, Rui Wu, Kai Zhu, Bruce Hajek, R. Srikant, Lei Ying

Abstract: In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we propose three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade-offs: one can gradually reduce the computational complexity when increasingly more observations are available.

1. Introduction

Biclustering involves the simultaneous recovery of row and column clusters in a data matrix. This problem is prevalent in applications such as recommender systems (clustering users and items) and bioinformatics (clustering patients and genes). This paper focuses on binary matrices with block-constant structures, where observations are sparse and corrupted by noise. The central question is determining the minimum number of observations $m$ required for exact recovery and how this requirement scales with the computational complexity of the chosen algorithm.

2. Algorithmic Approaches

The authors evaluate four primary methods for cluster recovery, each representing a different point on the computational-statistical trade-off spectrum. These range from statistically optimal but computationally expensive combinatorial methods to highly efficient spectral methods that require more data for success.

Comparison of recovery methods across parameter regimes, observation requirements, and runtime.
  • Combinatorial Method: Minimizes the number of disagreements between the observed matrix and a block-constant candidate. It is statistically powerful but computationally intractable (exponential time).
  • Convex Method: Formulates the problem as a low-rank matrix completion task using nuclear norm regularization, converting a discrete problem into a solvable convex optimization.
  • Spectral Method: Employs Singular Value Decomposition (SVD) followed by a "joint clean-up" step to achieve exact recovery. It is the most computationally efficient of the proposed methods.
  • Nearest-Neighbor Clustering: A baseline that clusters rows/columns based on shared observed entries, which surprisingly can outperform convex methods in certain regimes.

3. Theoretical Limits and the Time-Data Trade-off

A key contribution of this work is the characterization of a "time-data trade-off." As more data (observations $m$) becomes available, the computational effort required for exact recovery decreases. The authors derive an information-theoretic lower bound of $m = O(n^{1.5}/K)$ for recovery, where $n$ is the matrix dimension and $K$ is the cluster size.

The success regimes for these algorithms are visualized in a phase diagram. The diagram maps the relationship between the number of clusters and the number of observations, highlighting the boundaries where each method succeeds.

Phase diagram illustrating the success boundaries for different recovery algorithms.

The "gap" between the combinatorial and polynomial-time methods suggests a regime where recovery is statistically possible but computationally difficult. Notably, the spectral method, while requiring the most data, offers the highest efficiency ($O(n^3)$), making it suitable for large-scale datasets. The paper provides the first theoretical guarantees for exact recovery using spectral methods with a growing number of clusters.

4. Discussion and Future Work

While the results provide a rigorous framework for biclustering, several open questions remain. The analysis of the convex method relies on an "Incoherence Conjecture" regarding the matrix's singular vectors, which is supported by simulations but lacks a formal proof. Additionally, extending these results from binary to real-valued matrices and analyzing the combinatorial method under high-noise conditions are promising avenues for future research.

Summary updated

Abstract

In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we propose three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade-offs: one can gradually reduce the computational complexity when increasingly more observations are available.
BibTeX
@inproceedings{xu2014jointly,
  author = {Jiaming Xu and Rui Wu and Kai Zhu and Bruce Hajek and R. Srikant and Lei Ying},
  title = {{Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs}},
  booktitle = {SIGMETRICS},
  year = {2014},
  doi = {10.1145/2591971.2592005},
}
Figure