Convex relaxation for the planted clique, biclique, and clustering problems

摘要: A clique of a graph G is set pairwise adjacent nodes G. Similarly, biclique (U, V ) bipartite pair disjoint, independent vertex sets such that each node in U to every We consider the problems identifying maximum graph, known as problem, and maximizes product |U | · |V |, edge problem. show finding or given size equivalent rank one matrix satisfying particular linear constraints. These can be formulated minimization relaxed convex programming by replacing with its envelope, nuclear norm. Both are NP-hard yet we our relaxation exact case input contains large plus additional edges. For provide two analyses when exact. In first, diversionary edges added deterministically an adversary. second, potential independently at random fixed probability p. case, bounds match earlier Alon, Krivelevich, Sudakov, well Feige Krauthgamer for extend these results techniques k-disjoint-clique The problem find k disjoint cliques containing number nodes. Given nonnegative weights w ∈ R+, mean weight seeks identify sum average edges, respect w, complete subgraphs induced cliques. may considered way pose clustering clustering, wants partition data so items cluster similar different clusters dissimilar. represents any if only corresponding similar, into partitioning k-disjoint indicating similarity between items, clustered solving both instances constrained optimization semidefinite programs using norm rank. also instance corresponds collection planted nodes, this problems. theoretical guarantee ex-