Non-Exhaustive, Overlapping Co-Clustering: An Extended Analysis

Joyce Jiyoung Whang, Inderjit S. Dhillon

Abstract

The goal of co-clustering is to simultaneously identify a clustering of rows as well as columns of a two dimensional data matrix. A number of co-clustering techniques have been proposed including information-theoretic co-clustering and the minimum sum-squared residue co-clustering method. However, most existing co-clustering algorithms are designed to find pairwise disjoint and exhaustive co-clusters while many real-world datasets contain not only a large overlap between co-clusters but also outliers which should not belong to any co-cluster. In this paper, we formulate the problem of Non-Exhaustive, Overlapping Co-Clustering where both of the row and column clusters are allowed to overlap with each other and outliers for each dimension of the data matrix are not assigned to any cluster. To solve this problem, we propose intuitive objective functions, and develop an an efficient iterative algorithm which we call the NEO-CC algorithm. We theoretically show that the NEO-CC algorithm monotonically decreases the proposed objective functions. Experimental results show that the NEO-CC algorithm is able to effectively capture the underlying co-clustering structure of real-world data, and thus outperforms state-of-the-art clustering and co-clustering methods. This manuscript includes an extended analysis of [21].

Introduction

In unsupervised learning, co-clustering is a powerful technique for simultaneously grouping the rows and columns of a data matrix. Common applications include grouping users with the movies they watch or genes with the biological conditions under which they are expressed. However, traditional co-clustering algorithms typically rely on two restrictive assumptions: exhaustiveness (every point must belong to a cluster) and disjointness (every point belongs to exactly one cluster).

Real-world data often violates these assumptions. For instance, a movie may belong to multiple genres (overlap), and some users may provide noisy, random ratings that do not fit any pattern (outliers). Forcing such data into rigid, disjoint boxes degrades cluster quality. This paper introduces the Non-Exhaustive, Overlapping Co-Clustering (NEO-CC) framework to address these challenges by allowing for overlaps and outliers in both dimensions simultaneously.

Methodology

The authors propose a unified framework that generalizes existing methods like Minimum Sum-Squared Residue (MSSR) co-clustering. Two primary objective functions are introduced:

  1. NEO-CC-M (Mean-based): Minimizes the squared difference between a matrix entry and the mean of the co-clusters it belongs to.
  2. NEO-CC-RCM (Row and Column Mean-based): Incorporates row and column biases, similar to bias removal in recommender systems, to account for individual variations (e.g., generous vs. harsh raters).
Illustration of the objective function calculation for overlapping co-clusters, showing how residuals are computed relative to cluster means.

The NEO-CC algorithm is an iterative, alternating procedure that updates row assignments while keeping column assignments fixed, and vice versa. The model uses four parameters ($\alpha_r, \beta_r, \alpha_c, \beta_c$) to control the budget for overlaps and outliers. Crucially, the authors provide a mathematical proof that the algorithm monotonically decreases the objective functions, ensuring convergence to a local optimum.

Experimental Evaluation

The performance of NEO-CC was evaluated against state-of-the-art methods using MovieLens rating datasets and Yeast gene expression data.

  • MovieLens: Since movies often span multiple genres, this dataset is ideal for testing overlapping clusters. NEO-CC achieved an $F_1$ score of 58.4% on the ML1 dataset, significantly outperforming the non-overlapping MSSR baseline (44.2%).
  • Yeast Gene Expression: NEO-CC-M achieved the highest $F_1$ score (40.7%), demonstrating its ability to identify genes with multiple functional roles.
Comparison between the original data matrix (a) and the matrix rearranged using the NEO-CC method (b), demonstrating the emergence of clear block structures.

A key insight from the experiments is the algorithm's robustness to noise. By allowing for non-exhaustiveness, NEO-CC can effectively "ignore" outliers, such as users with random rating patterns, which leads to much clearer and more stable cluster identification compared to Bayesian models like the Infinite Plaid Model (IPM).

Conclusion and Future Work

NEO-CC provides a flexible, unified framework for co-clustering that handles the complexities of real-world data. While the current iterative algorithm is efficient, future work may explore even more scalable procedures for massive datasets or adapt Semidefinite Programming (SDP) approaches to further enhance cluster quality. The ability to manage complicated interactions between overlapping row and column sets makes NEO-CC a significant advancement over traditional one-way or disjoint co-clustering methods.

Summary updated

Abstract

The goal of co-clustering is to simultaneously identify a clustering of rows as well as columns of a two dimensional data matrix. A number of co-clustering techniques have been proposed including information-theoretic co-clustering and the minimum sum-squared residue co-clustering method. However, most existing co-clustering algorithms are designed to find pairwise disjoint and exhaustive co-clusters while many real-world datasets contain not only a large overlap between co-clusters but also outliers which should not belong to any co-cluster. In this paper, we formulate the problem of Non-Exhaustive, Overlapping Co-Clustering where both of the row and column clusters are allowed to overlap with each other and outliers for each dimension of the data matrix are not assigned to any cluster. To solve this problem, we propose intuitive objective functions, and develop an an efficient iterative algorithm which we call the NEO-CC algorithm. We theoretically show that the NEO-CC algorithm monotonically decreases the proposed objective functions. Experimental results show that the NEO-CC algorithm is able to effectively capture the underlying co-clustering structure of real-world data, and thus outperforms state-of-the-art clustering and co-clustering methods. This manuscript includes an extended analysis of [21].
BibTeX
@inproceedings{whang2017non,
  author = {Joyce Jiyoung Whang and Inderjit S. Dhillon},
  title = {{Non-Exhaustive, Overlapping Co-Clustering: An Extended Analysis}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2017},
  url = {https://openreview.net/forum?id=socPObP6OW7},
}
Figure