{"id":{"repo_id":"alabama","oai_identifier":"oai:ir.ua.edu:123456789/17099"},"canonical_url":"https://search.dev.ndltd.org/etd/alabama/oai:ir.ua.edu:123456789/17099","repository":{"repo_id":"alabama","name":"University of Alabama","base_url":"https://ir-api.ua.edu/oai/request"},"display":{"title":"Perfect Recovery in Heterogeneous Stochastic Bicluster Models","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sumonu, Abiodun Olalekan"],"institution":"University of Alabama Libraries","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Zhu, Wei","Wang, Chuntian","Sun, Min"],"advisors":["Sidje, Roger B","Ames, Brendan P"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-07-27T18:44:22Z","subjects":[],"languages":["en_US","English"],"rights":["All rights reserved by the author unless otherwise indicated."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["1178265"],"render_values":[{"text":"1178265","href":null,"code":true}]}]},"links":{"outbound_url":"https://ir.ua.edu/handle/123456789/17099","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Zhu, Wei","Wang, Chuntian","Sun, Min"]},{"key":"dc:contributor.advisor","label":"Advisor","values":["Sidje, Roger B","Ames, Brendan P"]},{"key":"dc:creator","label":"Author","values":["Sumonu, Abiodun Olalekan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-09-04T16:14:49Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-09-04T16:14:49Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:publisher","label":"Institution","values":["University of Alabama Libraries"]},{"key":"dc:type","label":"Dc Type","values":["thesis","text"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["All rights reserved by the author unless otherwise indicated."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["1178265"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://ir.ua.edu/handle/123456789/17099"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Electronic Thesis or Dissertation"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["electronic"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Perfect Recovery in Heterogeneous Stochastic Bicluster Models"]}]}],"canonical_facts":{"dc:contributor":["Zhu, Wei","Wang, Chuntian","Sun, Min"],"dc:contributor.advisor":["Sidje, Roger B","Ames, Brendan P"],"dc:creator":["Sumonu, Abiodun Olalekan"],"dc:date.accessioned":["2025-09-04T16:14:49Z"],"dc:date.available":["2025-09-04T16:14:49Z"],"dc:date.issued":["2026"],"dc:description":["Electronic Thesis or Dissertation"],"dc:description.abstract":["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."],"dc:format.medium":["electronic"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["1178265"],"dc:identifier.uri":["https://ir.ua.edu/handle/123456789/17099"],"dc:language":["English"],"dc:language.iso":["en_US"],"dc:publisher":["University of Alabama Libraries"],"dc:rights":["All rights reserved by the author unless otherwise indicated."],"dc:title":["Perfect Recovery in Heterogeneous Stochastic Bicluster Models"],"dc:type":["thesis","text"]},"updated_at":"2026-07-27T18:44:22Z"}