Convex optimization for the planted \(k\)-disjoint-clique problem (Q2436653)

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.