Home | Publications | AA25

Rank-Sparsity Decomposition for Planted Quasi Clique Recovery

MCML Authors

Sakirudeen Abdulsalaam

Dr.

→ Group Holger Rauhut
Mathematical Data Science and Artificial Intelligence

Abstract

In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has the planted Maximum Clique Problem (MCP) as a special case. The maximum clique problem is NP-hard. A Quasi-clique or -clique is a dense graph with the edge density of at least , . The maximum quasi-clique problem seeks to find such a subgraph with the largest cardinality in a given graph. Our method of choice is the low-rank plus sparse matrix splitting technique. We present a theoretical basis for when our convex relaxation problem recovers the planted maximum quasi-clique. We have derived a new bound on the norm of the dual matrix that certifies the recovery using norm. We have showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we have performed corroborate our theoretical findings.

article AA25