  We consider the problem of identifying a maximum clique in a given graph. We
have proposed a mathematical model for this problem. The model resembles the
matrix decomposition of the adjacency matrix of a given graph. The objective
function of the mathematical model includes a weighted $\ell_{1}$-norm of the
sparse matrix of the decomposition, which has an advantage over the known
$\ell_{1}-$norm in reducing the error. The use of dynamically changing the
weights for the $\ell_{1}$-norm has been motivated. We have used proximal
operators within the iterates of the ADMM (alternating direction method of
multipliers) algorithm to solve the optimization problem. Convergence of the
proposed ADMM algorithm has been provided. The theoretical guarantee of the
maximum clique in the form of the low-rank matrix has also been established
using the golfing scheme to construct approximate dual certificates. We have
constructed conditions that guarantee the recovery and uniqueness of the
solution, as well as a tight bound on the dual matrix that validates optimality
conditions. Numerical results for planted cliques are presented showing clear
advantages of our model when compared with two recent mathematical models.
Results are also presented for randomly generated graphs with minimal errors.
These errors are found using a formula we have proposed based on the size of
the clique. Moreover, we have applied our algorithm to real-world graphs for
which cliques have been recovered successfully. The validity of these clique
sizes comes from the decomposition of input graph into a rank-one matrix
(corresponds to the clique) and a sparse matrix.
