Guaranteed clustering and biclustering via semidefinite programming

Abstract

Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest k-disjoint-clique problem, whose goal is to identify the collection of k disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest k cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of k large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation for the biclustering problem with similar recovery guarantees. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as partitioning the nodes of a weighted bipartite complete graph such that the sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest k-disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.

References in corpus (2)

• Finding Dense Clusters via "Low Rank + Sparse" Decomposition
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim

Cited by in corpus (26)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Community structure: A comparative evaluation of community detection methods
• Improved Graph Clustering
• Binary Optimization via Mathematical Programming with Equilibrium Constraints
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Learning Communities in the Presence of Errors
• Profile Likelihood Biclustering
• Information Limits for Recovering a Hidden Community
• Relax, no need to round: integrality of clustering formulations
• Recovery guarantees for exemplar-based clustering
• Convex relaxation for finding planted influential nodes in a social network
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• A Simple Spectral Algorithm for Recovering Planted Partitions
• Exact and Heuristic Algorithms for Constrained Biclustering
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models
• Goodness-of-fit Test for Latent Block Models
• Crowdsourced Labeling for Worker-Task Specialization Model
• K-median: exact recovery in the extended stochastic ball model
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering