Convex optimization for the planted k-disjoint-clique problem

DOI10.1007/S10107-013-0733-1MaRDI QIDQ2436653zbMATH OpenOpenAlexFDO

Authors Stephen A. Vavasis, Brendan P. W. Ames

Publication date 25 February 2014

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.2814

zbMATH Keywords

combinatorial optimizationsemidefinite programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Abstract: We consider the k-disjoint-clique problem. The input is an undirected graph G in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph k disjoint cliques that cover the maximum number of nodes of G. This problem may be understood as a general way to pose the classical `clustering' problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows `noise' nodes to be present in the input data that are not part of any of the cliques. The k-disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of k disjoint large cliques (called `planted cliques') that are then obscured by noise edges and noise nodes inserted either at random or by an adversary.

Review text

The authors consider the clustering problem for graphs. More precisely, given an undirected graph, the problem is to find a certain number of disjoint cliques that cover the maximum number of nodes of the graph. This problem has numerous potential applications, since clustering aims at partitioning data into sets of similar objects. Whereas the exact clustering problem considered by the authors is NP-hard, it is approached with a convex relaxation that can solve it in polynomial time in some specific cases which, as argued by the authors, are practically relevant. These cases include graphs consisting of a certain number of disjoint large cliques perturbed by some diversionary nodes and edges added either randomly (noise) or by an adversary. The classical convex relaxation approach followed by the authors consists of formulating the underlying combinatorial optimization problem as a (linear hence convex) semidefinite programming problem with a (nonconvex) rank constraint, and then relaxing the problem by dropping the rank constraint. Under the assumption that there is a solution of given rank (which corresponds to the existence of an unperturbed graph consisting of disjoint large cliques, and a bound on the number of noise edges, see the main result Theorem 3.1), the authors can prove a posteriori that the convex relaxation exactly recovers the combinational solution by constructing dual multipliers.

Recommendations

• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Convex optimization for the densest subgraph and densest submatrix problems
• Guaranteed clustering and biclustering via semidefinite programming
• Clustering partially observed graphs via convex optimization
• Exact clustering of weighted graphs via semidefinite programming

Cites work

• A limit theorem for the norm of random matrices
• A Newton-CG augmented Lagrangian method for semidefinite programming
• Clustering partially observed graphs via convex optimization
• Exact matrix completion via convex optimization
• Finding and certifying a large hidden clique in a semirandom graph
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Nuclear norm minimization for the planted clique and biclique problems
• Probability and Computing
• Probability Inequalities for Sums of Bounded Random Variables
• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust principal component analysis?
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• The eigenvalues of random symmetric matrices

Cited in

(19)

• Convex optimization for the densest subgraph and densest submatrix problems
• On semidefinite relaxations for the block model
• Polyhedral properties of the induced cluster subgraphs
• Convex relaxation methods for community detection
• The maximum independent union of cliques problem: complexity and exact approaches
• On the hardness of designing public signals
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Convexified modularity maximization for degree-corrected stochastic block models
• Clustering partially observed graphs via convex optimization
• Approximate global minimizers to pairwise interaction problems via convex relaxation
• Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
• Exact clustering of weighted graphs via semidefinite programming
• Guaranteed clustering and biclustering via semidefinite programming
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• k-median: exact recovery in the extended stochastic ball model
• Rank-sparsity decomposition for planted quasi clique recovery
• The Lovász theta function for recovering planted clique covers and graph colorings
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Recovery guarantees for exemplar-based clustering

This page was built for publication: Convex optimization for the planted \(k\)-disjoint-clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436653)