Perfect Recovery in Heterogeneous Stochastic Bicluster Models

Unlike traditional clustering, which groups only objects based on similarity, biclustering simultaneously partitions both objects and features into subgroups, known as biclusters, based on their expression patterns. We model this as the densest k-disjoint-biclique problem, in which a weighted complete bipartite graph is partitioned into k disjoint subgraphs to maximize the sum of their densities. In our first solution approach, we show that underlying bicliques can be recovered with high probability by solving a particular semidefinite relaxation, provided the input graph is drawn from a heterogeneous planted–bicluster model. We proceed to derive necessary and sufficient conditions for exact recovery, then via numerical simulations, we explore the impact of sparsity, weight distributions, block sizes, and outliers on the semidefinite relaxation performance. Our results reveal sharp phase transitions, identifying critical thresholds for perfect recovery of the planted structure. In the noiseless regime, i.e., when all inter-cluster edges carry negligible or zero weight, the semidefinite relaxation is exact whenever the graph contains k large, dense, disjoint bicliques. When noise is present (i.e., nonzero between-cluster weights), we show that significantly smaller biclusters remain recoverable if inter-cluster weights are sufficiently small or sparse. In fact, for approximately sparse graphs where inter-cluster weights vanish as min{m, n} becomes large, we prove recovery of biclusters whose size grows only polylogarithmically in min{m, n}, under mild distributional assumptions. As an alternative to the semidefinite relaxation, we also reformulated the k-disjoint-biclique problem as an orthogonality-constrained optimization problem and apply an extended Bregman-iteration splitting method (after Lai & Osher) to jointly recover object and feature clusters. Extensive experiments confirm the theoretical phase transition boundaries and demonstrate the practical effectiveness of both methods.

Grantor dc:publisher

University of Alabama Libraries

Year dc:date.issued

2026

Author dc:creator

• Sumonu, Abiodun Olalekan

Advisors dc:contributor.advisor

• Sidje, Roger B
• Ames, Brendan P

Contributors dc:contributor

• Zhu, Wei
• Wang, Chuntian
• Sun, Min

Statement dc:rights

• All rights reserved by the author unless otherwise indicated.

Language dc:language.iso

en_US, English

Dc Identifier Other

1178265

OAI identifier oai:identifier

oai:ir.ua.edu:123456789/17099