Learning A Structured Optimal Bipartite Graph for Co-Clustering

Feiping Nie, Xiaoqian Wang, Cheng Deng, Heng HuangNeurIPS 2017 · OpenReview

Overview

This paper introduces a novel co-clustering method that learns a bipartite graph with a built-in, explicit cluster structure. By mathematically forcing the graph to have exactly $k$ connected components, the researchers eliminate the need for unstable post-processing steps like K-means. This approach results in significantly higher clustering accuracy and remarkable robustness to noise.

The Problem with Traditional Co-Clustering

In many complex datasets, there is a natural duality between samples and features. For example, in document analysis, documents are defined by the words they contain, but word clusters are simultaneously defined by the documents in which they appear. Co-clustering (or bi-clustering) seeks to group both dimensions simultaneously to exploit this reciprocal relationship.

Most existing graph-based co-clustering methods construct a bipartite graph to map these relationships and then use spectral clustering to find partitions. However, these standard methods produce a "fuzzy" graph that lacks a definitive cluster structure. To obtain actual cluster assignments, researchers typically must run K-means clustering on the resulting embeddings. This two-step process is problematic because K-means is highly sensitive to initialization, often leading to unstable and suboptimal results. The authors aim to solve this by learning a graph that is already "pre-partitioned" into the desired number of clusters.

Methods: Structured Optimal Bipartite Graph (SOBG)

The authors propose the Structured Optimal Bipartite Graph (SOBG) model. Their approach hinges on an elegant property of graph theory: the number of connected components in a graph is exactly equal to the multiplicity of the eigenvalue 0 in its Laplacian matrix.

Transformation from a standard bipartite graph to a structured optimal bipartite graph with clear clusters.

Key technical highlights of SOBG include:

  • Rank Constraint: The authors formulate an optimization problem that minimizes the distance between the original data and a new bipartite graph, subject to a strict constraint: the Laplacian of the new graph must have a rank of $n - k$ (where $n$ is the total number of nodes and $k$ is the target number of clusters).
  • Direct Clustering: Because the learned graph is mathematically forced to have exactly $k$ connected components, the clustering results can be read directly from the graph's structure. This entirely bypasses the need for post-processing steps like K-means.
  • Algorithmic Efficiency: Solving eigen-decomposition on a large $(n_1 + n_2) \times (n_1 + n_2)$ matrix is computationally expensive. To address this, the authors derive a "speed-up" version of their algorithm that uses Singular Value Decomposition (SVD) on the much smaller $n_1 \times n_2$ data matrix, making the method practical for larger datasets.

Key Insights and Results

The model was evaluated on synthetic datasets with varying noise levels, the Reuters21578 document dataset, and several bioinformatics gene expression datasets (LUNG, Prostate-MS, and prostateCancerPSA410).

  • Structure as a Prior: Instead of treating clustering as a secondary step after graph learning, this paper treats the existence of clusters as a fundamental constraint of the learning process itself.
  • Robustness to Noise: By enforcing a global structure (exactly $k$ components), the model is far less likely to be led astray by local noise. In synthetic tests with extreme noise (0.9), SOBG maintained ~84% accuracy, while traditional methods like K-means and Normalized Cut plummeted to ~39%.
Clustering accuracy comparison on synthetic data across varying noise levels.
  • Superior Real-World Accuracy: On the Reuters21578 dataset, SOBG achieved an accuracy of 43.94%, significantly outperforming the next best method, K-means (which peaked at 32.77%).
  • Stability in High Dimensions: The authors noted that their advantage becomes more pronounced in high-dimensional data, such as gene expression profiles. In these scenarios, traditional distance metrics often become "vague," but the structured graph approach remains highly robust.

Limitations and Future Work

While highly effective, the SOBG model has a few limitations:

  • Hyperparameter Tuning: The model relies on a penalty parameter $\lambda$. While the authors suggest a heuristic to update $\lambda$ automatically based on the number of zero eigenvalues, it still requires an initial guess and iterative adjustments.
  • Fixed $k$: Like most spectral methods, the number of clusters $k$ must be known or estimated beforehand. The model does not currently discover the optimal number of clusters autonomously.
  • Computational Scaling: Although the SVD optimization improves efficiency, the method remains iterative. Scaling to massive datasets with millions of samples or features would likely require further approximation techniques or stochastic optimization strategies.

Summary updated

Abstract

Co-clustering methods have been widely applied to document clustering and gene expression analysis. These methods make use of the duality between features and samples such that the co-occurring structure of sample and feature clusters can be extracted. In graph based co-clustering methods, a bipartite graph is constructed to depict the relation between features and samples. Most existing co-clustering methods conduct clustering on the graph achieved from the original data matrix, which doesn’t have explicit cluster structure, thus they require a post-processing step to obtain the clustering results. In this paper, we propose a novel co-clustering method to learn a bipartite graph with exactly k connected components, where k is the number of clusters. The new bipartite graph learned in our model approximates the original graph but maintains an explicit cluster structure, from which we can immediately get the clustering results without post-processing. Extensive empirical results are presented to verify the effectiveness and robustness of our model.
BibTeX
@inproceedings{nie2017learning,
  author = {Feiping Nie and Xiaoqian Wang and Cheng Deng and Heng Huang},
  title = {{Learning A Structured Optimal Bipartite Graph for Co-Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=S1V-2wZObB},
}
Figure