![[2508.05493] Exact and Heuristic Algorithms for Constrained Biclustering](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2508.05493] Exact and Heuristic Algorithms for Constrained Biclustering
Summary
This paper presents exact and heuristic algorithms for constrained biclustering, enhancing data matrix analysis by incorporating prior knowledge to improve clustering outcomes.
Why It Matters
The study addresses the growing need for advanced clustering techniques in machine learning and optimization, particularly in scenarios where prior knowledge can enhance the interpretability and quality of data analysis. The proposed algorithms could significantly impact fields that rely on data clustering, such as bioinformatics and social network analysis.
Key Takeaways
- Introduces constrained biclustering, enhancing traditional clustering methods.
- Presents both exact and heuristic algorithms for improved performance.
- Demonstrates significant performance improvements over general-purpose solvers.
- Utilizes semidefinite programming and integer programming techniques.
- Offers practical solutions for large-scale data analysis challenges.
Mathematics > Optimization and Control arXiv:2508.05493 (math) [Submitted on 7 Aug 2025 (v1), last revised 23 Feb 2026 (this version, v2)] Title:Exact and Heuristic Algorithms for Constrained Biclustering Authors:Antonio M. Sudoso View a PDF of the paper titled Exact and Heuristic Algorithms for Constrained Biclustering, by Antonio M. Sudoso View PDF Abstract:Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns. Incorporating background knowledge into clustering to enhance solution quality and interpretability has attracted growing interest in mathematical optimization and machine learning research. Extending this paradigm to biclustering enables prior information to guide the joint grouping of rows and columns. We study constrained biclustering with pairwise constraints, namely must-link and cannot-link constraints, which specify whether objects should belong to the same or different biclusters. As a model problem, we address the constrained version of the k-densest disjoint biclique problem, which aims to identify k disjoint complete bipartite subgraphs (called bicliques) in a weighted complete bipartite graph, maximizing the total density while satisfying pairwise constraints. We propose both exact and heuristic algorithms. The exact approach is a tailored branch-and-cut algorithm based on a low-dimensional semidefinite programming (SDP) relaxation, s...
